Multiply

In base 10, 6 × 9 = 42 is false, but in base 13 it is true. In base 13, 42 equals 4 × 13^1 + 2 × 13^0 = 54, which is also the decimal value of 6 × 9.

You are given three integers p, q, and r, each written only with decimal digits. Find a base B (2 ≤ B ≤ 16) such that, when all three numbers are interpreted in base B, the equation p × q = r is true. If more than one base works, output the smallest one.

For instance, if p = 11, q = 11, and r = 121, the equation is true in base 3. It is also true in base 10, but the smallest valid base is 3. If no valid base exists, output 0.

The first line contains the number of test cases T. Each of the next T lines contains three integers p, q, and r, separated by spaces.

Every character in p, q, and r is a digit from 0 to 9. Interpreted as decimal integers, they satisfy 1 ≤ p, q, r ≤ 1,000,000.

For each test case, print one integer on its own line. Print the smallest base B for which p × q = r is true, or print 0 if no such base exists.