3232번 - Multiply 다국어

문제

“6 × 9 = 42” is not true for base 10, but is true for base 13. That is, 6₍₁₃₎ × 9₍₁₃₎ = 42₍₁₃₎ because 42₍₁₃₎ = 4 × 13¹ + 2 × 13⁰ = 54₍₁₀₎.

You are to write a program which inputs three integers p, q, and r and determines the base B (2 ≤ B ≤ 16) for which p × q = r. If there are many candidates for B, output the smallest one. For example, let p = 11, q = 11, and r = 121. Then we have 11₍₃₎ × 11₍₃₎ = 121₍₃₎ because 11₍₃₎ = 1 × 3¹ + 1 × 3⁰ = 4₍₁₀₎ and 121₍₃₎ = 1 × 3² + 2 × 3¹+ 1 × 3⁰ = 16₍₁₀₎. For another base such as 10, we also have 11₍₁₀₎ × 11₍₁₀₎ = 121₍₁₀₎. In this case, your program should output 3 which is the smallest base. If there is no candidate for B, output 0.

입력

The input consists of T test cases. The number of test cases (T ) is given in the first line of the input file. Each test case consists of three integers p, q, and r in a line. All digits of p, q, and r are numeric digits and 1 ≤ p, q, r ≤ 1,000,000.

출력

Print exactly one line for each test case. The line should contain one integer which is the smallest base for which p × q = r. If there is no such base, your program should output 0.

제한

힌트