暂无测试数据。

题目描述

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