暂无测试数据。

题目描述

6*9 = 42 对于十进制来说是错误的，
但是对于 13 进制来说是正确的。

即6(13) * 9(13)=42(13)，
而 42(13) = 4*13 + 2*1 = 54(10)。

你的任务是写一段程序读入三个整数 \(p\)、\(q\)和 \(r\)，
然后确定一个进制 \(B\) ( \(2 \leq B \leq 16\)) 使得 \(p*q=r\)。

如果 \(B\) 有很多选择，则输出最小的一个。

例如：
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。
如果没有合适的进制，则输出 0。

输入

一行，包含三个整数 \(p\)、\(q\)、\(r\)，相邻两个整数之间用单个空格隔开。

输出

一个整数：即使得 \(p*q=r\) 成立的最小的B。
如果没有合适的 \(B\)，则输出 0。

样例输入

6 9 42

样例输出

13

数据范围限制

\(p\)、\(q\)、\(r\) 的所有位都是数字，并且 \(1 \leq p、q、r \leq 10^6\)。

来源

基础篇练习7.1