题目描述

$"6 * 9 = 42"$ 在十进制（基数为$10$）下不成立，但在基数为$13$时成立。即，$6(13) * 9(13) = 42(13)$，因为 $42(13) = 4 * 13¹ + 2 * 13⁰ = 54(10)$。

你需要编写一个程序，输入三个整数 $p、q 和 r$，并确定满足$p * q = r$ 的基数 $B（2 ≤ B ≤ 16）$。如果有多个可能的 $B$，输出最小的一个。例如，当 $p = 11、q = 11、r = 121$时，$$11(3) * 11(3) = 121(3)$$ 成立，因为：

而对于基数$10$，同样有 $11(10) * 11(10) = 121(10)$。此时，你的程序应输出最小的基数 $3$。如果没有满足条件的 $B$，则输出 $0$。

输入

输入包含 $T$ 个测试用例。测试用例的数量 $T$ 在第一行给出。每个测试用例由一行中的三个整数 $p、q 和 r$ 组成。$p、q 和 r$的所有字符均为数字，且 $1 ≤ p, q, r ≤ 1,000,000$。

输出

对于每个测试用例，输出一行，包含一个整数，即满足 $p * q = r$的最小基数 $B$。如果没有这样的基数，则输出 $0$。

输入样例

3
6 9 42
11 11 121
2 2 2

输出样例

13
3
0

题目来源

Taejon 2002