BSMATH2 - Math with Bases

With your previous help, Little Ben managed to get a perfect score on his homework. He came running home to show his brother, Big Ben. Big Ben had done this type of thing before, you see, so he naturally wasn't too impressed. Big Ben boasted, "Back in my day, we had to multiply and divide as well, the numbers were much bigger, AND we had to do it in base 64."

Little Ben became intrigued by this and searched the Internet for a worksheet. It turns out that his teacher made a worksheet for one of the higher grades that was just like Big Ben's. She also forgot to write what base each question was in... again!

According to the worksheet,

The digits used for Base 64 are the same as that of Base 62, with the single- and double-quotes as the last two; the digits used are 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'".

Input

The first line of input contains an integer n (1 < n < 64) that indicates the amount of sections (test cases). Each test case is as follows:

A - B = C
I
X1 op Y1 =
X2 op Y2 =
...
XI op YI =

where A - B = C is the correct example, I (1 ≤ I ≤ 5000) is the number of questions in that section, Xi and Yi are the operands of each problem (0 < X, Y ≤ 2100), and op is one of
[+, -, *, %], denoting addition, subtraction, multiplication, or modulo.


Output

Your program should output in the following format:

SECTION 1 (BASE b)
X1 op Y1 = Z1
X2 op Y2 = Z2
...
Xi op Yi = Zi
SECTION 2 (BASE b)
X1 op Y1 = Z1
X2 op Y2 = Z2
...
Xi op Yi = Zi
...
SECTION N (BASE b)
X1 op Y1 = Z1
X2 op Y2 = Z2
...
Xi op Yi = Zi

where Zi is the solution to Xi op Yi, and b is the base used. (2 ≤ b ≤ 64). If the base is ambiguous, use the smallest base for which the example is correct and the questions are valid.

Example

Input:

4
K72Q - 9C5U = APRR
3
11JH4 - BMEB =
PB04 % DQ9O =
F0GM - UQR0 =
A654A - 9A60E = AE3B
2
B94BA + 3460A =
123A29 % 5E065 =
37CR - olh = 2KSm
5
157W % 1bIJ =
1P56 % 1Eob =
1C6I * 1"uX =
1Ktc % 1BMf =
20ne * 22V" =
BQfC - 4Kdb = 761H
2
9aFL * 3WU3 =
5fcV + 7fWL =

Output:

SECTION 1 (BASE 31)
  11JH4 - BMEB = KS2O
  PB04 % DQ9O = BFLB
  F0GM - UQR0 = -FQA9
SECTION 2 (BASE 15)
  B94BA + 3460A = EDAC5
  123A29 % 5E065 = 5594E
SECTION 3 (BASE 64)
  157W % 1bIJ = 157W
  1P56 % 1Eob = AIX
  1C6I * 1"uX = 2O3gS"I
  1Ktc % 1BMf = 9Wz
  20ne * 22V" = 46bA3EO
SECTION 4 (BASE 42)
  9aFL * 3WU3 = bBafS4L
  5fcV + 7fWL = DfTA

Notes: large input/output data


Added by:Jargon
Date:2009-12-10
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Own problem

hide comments
2020-02-07 07:47:26 Simes
Hey, mine too!
2020-02-07 02:18:52
Whoa! My solution that TLE'd in 2017 now gets AC, unchanged! Thanks supernanren for Py-validating it =)
2012-09-03 16:44:06 (Tjandra Satria Gunawan)(曾毅昆)
time limit is too strict... my big-num mod algo in C is slow... :-(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.