确定数制

1. 今日内容

问题描述
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。若存在多个符合条件的进制，则输出其中最小的一个。例如：p = 11、q = 11、r = 121 的情况下，有等式成立的情况出现在进制为三时，即：11(3) * 11(3) = 121(3)，因为此时的数值转换为十进制后分别为：4(10) 和 16(10)。对于进制为十的情况，则有：p 和 q 的值均为十进制下的数值，其乘积也等于 r 的值。此时应输出最小的进制三。如果没有任何一种进制满足条件，则输出零。

输入数据
输入包含 T 组测试样例，在第一行给出 T 的值。每组测试样例占一行，包含三个整数 p、q 和 r。这些数字的所有位数均为有效数字，并且满足范围限制：p、q、r ≥ 一且 ≤ 百万。

输出要求
针对每组测试样例输出一行结果，该行包含一个整数 B，即满足等式 p*q=r 的最小可能的进制值；若不存在这样的 B，则输出零。

输入样例
3
6