Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Archaeologist John and his team have unearthed the remains of an ancient civilisation. The partially destroyed walls of its houses contain strange pairs of numbers. John assumes that the first number in each pair always corresponds to a base (itself written in base $10$) and the second number in that pair is written in this base ― for example, 3 2110 denotes $(2110)_3 = 2 \cdot 3^{3} + 1 \cdot 3^{2} + 1 \cdot 3 + 0 = 66$.

Unfortunately, the first number (the base) is often lost or unreadable. John made a list of pairs of numbers found on the walls, where he represents lost bases by $-1$. For example:

-1 10001
3 2110
-1 18565

John is wondering if all these pairs of numbers could represent a single common number ― that is, if it is possible to choose some number $X$ in decimal representation (in base $10$) and fill in all missing bases in such a way that the second numbers in all pairs written on the walls, when converted from their bases to base $10$, are equal to $X$. For each pair with a missing base $(-1, Y)$, we may choose any integer base $B$ such that $2 ≤ B ≤ 36$ and $Y$ is a valid number in base $B$.

Since John does not want to deal with huge numbers, he considers $X > 10^{12}$ to be invalid. Still, there are too many possibilities, so he needs your help. Your task is to find the smallest common number $X$ that satisfies all conditions, or determine that no such common number exists.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
Each of the following $N$ lines contains an integer $B$ followed by a space and a string $Y$, describing a pair of numbers found on the walls; in the string $Y$, digits $10$ through $35$ (in base $10$) are represented by letters 'A' through 'Z'.

------ Output ------
For each test case, print a single line containing one integer ― the smallest possible common number $X$, or $-1$ if there is no valid common number.

------ Constraints ------
$1 ≤ T ≤ 200$
$1 ≤ N ≤ 100$
$2 ≤ B ≤ 36$ or $B = -1$
$Y$ contains only digits '0' through '9' and letters 'A' through 'Z'
for each pair $(B, Y)$ on the input, if $B \neq -1$, $Y$ is a valid number in base $B$
the length of string $Y$ is at most $40$

------ Subtasks ------
Subtask #1 (30 points): there is at least one pair $(B, Y)$ such that $B \neq -1$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------
2

3

-1 10000

8 20

-1 16

3

-1 10100

-1 5A

-1 1011010
----- Sample Output 1 ------
16

90
----- explanation 1 ------
Example case 1:
- $(10000)$ in base $2$ is $16$ in base $10$
- $(20)$ in base $8$ is $16$ in base $10$
- $(16)$ in base $10$ is $16$ in base $10$

Example case 2:
- $(10100)_3 = (90)_{10}$
- $(5\mathrm{A})_{16} = (90)_{10}$
- $(1011010)_2 = (90)_{10}$

见题面

见题面