ALIENS1 - Alien arithmetic

Little Johnny of Byteland has been kidnapped by aliens from the Andromeda galaxy! Johnny is currently locked in a small room inside an UFO, which has been parked in his backyard. Johnny is desperately trying to open the door of the room. He finds that the door asks a series of arithmetic questions: addition, subtraction, multiplication or exponentiation (the aliens don't know how to divide) of two given numbers. Johnny laughs aloud and thinks that it will be very easy to answer these questions and escape. But when he sees the questions, he realises that the aliens use base 42! Now Johnny has panicked and asks you to help him out.

Input

The first line of the input has a number T (<= 500), denoting the number of tests cases. T lines follows, each of the form A op B, where A and B are numbers in base 42 having up to 10000 digits without unnecessary zeros and op is either +, -, * or ^ denoting the operation to be performed. Base 42 numbers are denoted by:

'0' to '9' denotes 0 to 9

'A' to 'Z' denotes 10 to 35

'a' to 'f' denotes 36 to 41

Output

For each test case, output one line: the result of the required operation in base 42 modulo LIFE42, without any unnecessary zeros.

Example

Input:
11
a + a
e - A
91 * 89
AEIOU + abcd
A - B
b ^ 2
5 ^ 0
123 - 45
ABC * 10
6 - 6
0 ^ 0

Output:
1U
U
1W59
L6ZR
LIFD
WP
1
de
ABC0
0
1

Warning: large Input / Output data, be careful with certain languages.


Added by:Balajiganapathi S
Date:2011-03-26
Time limit:1s-2.262s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2014-09-03 01:06:53 Saurabh Jain
Can anyone tell me faster IO to scan and print string
2013-12-23 14:20:18 kancha
nice problem ... atlast ac :P
2011-03-27 07:20:57 Ravi Kiran
Tough one to optimise!Phew!
It may help to solve www.spoj.pl/problems/CSQUARE before you attempt this.
2011-03-26 14:15:39 Balajiganapathi S
The test data has been changed. All solutions have been rejudged and one accepted solution got WA. Sorry for the inconvenience caused.
2011-03-26 07:45:12 numerix
You are wrong. Read the output constraints ...
2011-03-26 04:15:05 abhijith reddy d
Correct me if I am wrong, Shouldn't the output for "AEIOU + abcd" be B9ELR.
Edit: Understood, Thanks.

Last edit: 2011-03-26 07:47:23
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.