题目描述

卡卡西看到了一个等式：$6 * 9 = 42$，他感到非常的困惑，他想 $6 * 9$ 应该等于 $54$ 啊！他去问了鸣人老师，原来这个乘法是在 $13$ 进制下的运算，而我们平时生活是 $10$ 进制下的。 我们在数字后面用小括号里的数字表示这个数字是多少进制下的，比如 $12(13)$ 表示的是 $13$ 进制下的 $12$ 。我们怎么把某个进制下的数转化为我们熟悉的十进制呢？

比如 $42(13)=4 * 13 + 1 * 2 = 54(10)$，$123(12)=1 * 12 * 12 + 2 * 12 + 3 * 1=171(10)$，$111(10)=1 * 10 * 10+1 * 10+1 * 1 = 111(10)$，发现规律了吗？

现在鸣人老师让卡卡西写一段程序读入三个整数 $a$、$b$ 和 $c$，然后确定一个进制 $B(2<=B<=16)$ 使得 $a * b = c$。 如果 $B$ 有很多选择, 输出最小的一个。

例如：$a = 11$，$b = 11$，$c = 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$。

你可以帮他解决吗？

输入格式

一行，包含三个整数 $a,b,c$，相邻两个整数之间用单个空格隔开。 $a,b,c$ 的所有位都是数字，并且 $a,b,c$ 的长度均不超过 $15$ 位。

输出格式

一个整数：即使得 $a * b = c$ 成立的最小的 $B$。如果没有合适的 $B$，则输出 $0$。($2<=B<=16$)

样例

6 9 42

13