Problem A
10 Kinds of People
Remember that joke about “10 kinds of people in the world”? In case you don’t:
There are 10 kinds of people in the world:
those who don’t understand binary,
those who think there are only binary and decimal,
and those who realize there are other bases.
This joke is about numbers in different bases, or radices. The notation for a number represented by digits $D$ in base $B$ is written as $D_B$. For example, $10_2$ is the binary number 10 (which equals 2 in decimal), and $10_3$ is the number 3 in decimal represented in base 3.
The joke is funny because $10_2 = 2_{10}$, but $10_3 = 3_{10}$, and $10_4 = 4_{10} = 100_2$.
In this problem, we will dig a little deeper into that idea. You are given two numbers without specified bases. Your task is to determine whether there exist bases for each number such that their decimal values are equal.
To represent a wider range of numbers, we use the following digit scheme:
-
digits 0–9 represent values 0–9,
-
letters a–z represent values 10–35,
-
letters A–Z represent values 36–61.
For example, $1Z_{62} = 62 + 61 = 123_{10}$.
We will consider bases from 2 up to 7500. Even though we may not have enough characters to represent all digits in these bases, we can still find bases that make two numbers equal.
For instance:
-
The numbers 10 and 4000 are equal if 10 is in base 4000 and 4000 is in base 10, since both equal 4000 in decimal.
-
Similarly, 10 and 4000 are equal if 10 is in base 500 and 4000 is in base 5, since both equal 500 in decimal.
Input
The first line contains an integer $N$, the number of pairs of numbers.
\[ 1 \le N \le 500 \]Each of the next $N$ lines contains two numbers $A$ and $B$. Each number consists of 1 to 5 characters chosen from [0–9, a–z, A–Z].
Output
For each pair, if there exist bases $a$ and $b$ such that $A_a = B_b$, output three decimal numbers:
\[ \text{decimal value of } A_a, \quad a, \quad b \]If there are multiple triples $(A_a, a, b)$ that satisfy $A_a = B_b$, any one of them will be accepted. Otherwise, output:
\[ \text{CANNOT MAKE EQUAL.} \]Reminder: $2 \le a, b \le 7500$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 11 10 1Z 123 10 4000 1111 3333 |
3 2 3 123 62 10 500 500 5 CANNOT MAKE EQUAL |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 75 4GH teH9x eR8LJ 231Tq jIhE7 NVWng Oiing |
11275 1610 48 490386017 64 76 CANNOT MAKE EQUAL CANNOT MAKE EQUAL |
