测试数据来自 system/1309

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　\(6 × 9 = 42\) 对于十进制来说是错误的，但是对于 13 进制来说是正确的。即 \(6_{13} × 9_{13} = 42_{13}\)，而\(42_{13} = 4 × 13^1 + 2 × 13^0 = 54_{10}\)。

　　你的任务是写程序读入三个整数 \(p,q\) 和 \(r\)，然后确定一个进制 \(B (2 ≤ B ≤ 16)\) 使得 \(p × q = r\)。如果 \(B\) 有很多选择，输出最小的一个，如果没有合适的进制，则输出 0。例如：\(p = 11, q = 11, r = 121\)。则 \(11_{3} × 11_{3} = 121_{3}\)， 因为 \(11_{3} = 1 × 3^1 + 1 × 3^0 = 4_{10}\) 和 \(121_{3} = 1 × 3^2 + 2 × 3^1 + 1 × 3^0 = 16_{10}\)。 对于 10 进制，也有 \(11_{10} × 11_{10} = 121_{10}\)。这种情况下，应该输出 3。

【输入格式】

　　输入有 \(T\) 组测试样例。 \(T\) 在第一行给出。
　　每一组数据包含三个整数 \(p,q,r\)。 \(p,q,r\) 的所有位都是数字。

【输出格式】

　　对于每个数据输出一行。该行包含一个整数：即使得 \(p × q = r\) 成立的最小的 \(B\)。如果没有合适的 \(B\)，则输出 0。

【输入输出样例】

　Input

3
6 9 42
11 11 121
2 2 2

　Output

13
3
0

【数据限制】

　　\(100\%\) 的数据满足 \(1 ≤ p,q,r ≤ 1,000,000\) 。

【来源】

　　Mr.he