You are Special Agent Joe A. Eliot, member of the Cyber Crime Division of the FBI. Recently, the Bureau has intercepted an increasing number of suspicious encrypted messages exchanged between two highly suspect individuals: Charles the Prince of Wales and Dom Duarte the Duke of Bragança, the heir to the Portuguese throne.

Besides the encrypted messages, the Bureau has intercepted some pairs of numbers exchanged over secure channels. The latest intercepted message, from the Duke to the Prince, was:

4D 79 20 49 73 61 62 65 6C 69 6E 68 61 20 69 73 20 70 72 65 67 6E 61 6E 74 20 61 67 61 69 6E 2E

while the numbers "1110" and "D" where exchanged at the same time.

After some investigations concerning the encryption methods used, the Bureau is now certain that it relies on a very simple schema concerning the base associated with the numbers. Remarkably, by noticing that 1110 in base 2 and D in base 14 represent the same value (i.e., 1110₂=D₁₄), and subsequently interpreting each number in the message as being written in base 16 (the sum of the two determined bases), the Bureau has deciphered the message as:

My Isabelinha is pregnant again.

Problem

Write a program that, given a sequence of pairs of numbers, X and Y, determines, for each pair, the smallest base for X and the smallest base for Y so that X and Y represent the same value.

Input

The first line contains an integer N (1 <= N <= 2000), written in base 10, which is the length of the sequence of pairs.

Each of the following N lines contains two numbers, X and Y, separated by a space.

The bases associated with X and Y will be between 2 and 36 (inclusive). In representing these numbers:

• the digits 0 through 9 have their usual decimal interpretations, and

• the uppercase alphabetic characters A through Z represent digits with values 10 through 35, respectively.

It is known that both X and Y, when converted to base 10, are not greater than 1000000.

The output consists of N lines. The i^th line contains a message similar to those shown in the example below, which:

• either indicates the smallest base for X and the smallest base for Y (likely different from that for X) so that X and Y represent the same value;

• or states that the two numbers cannot be equal, regardless of the assumed base for each.

7 
12 5 
10 A 
12 34 
123 456 
1 2 
10 2
Z 35

12 (base 3) = 5 (base 6) 
10 (base 10) = A (base 11) 
12 (base 17) = 34 (base 5) 
123 is not equal to 456 in any base 2..36 
1 is not equal to 2 in any base 2..36 
10 (base 2) = 2 (base 3)
Z (base 36) = 35 (base 10)