题目描述

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

即, $\red{ 6_{13} * 9_{13} = 42_{13} }$， 而 $\red{42_{13} = 4*13^1 + 2*13^0 =54_{10} }$。

你的任务是写一段程序，读入三个整数$\red{p}$、$\red{q}$和 $\red{r}$， 然后确定一个进制 $\red{B}$($\red{2≤B≤40}$) 使得 $\red{p * q = r}$。 如果 $\red{B}$ 有很多选择, 输出最小的一个。

例如：$\red{p=11, q=11, r=121}$.

则有$\red{11_3 * 11_3 = 121_3 }$ 因为 $\red{11_3 = 1*3^1+1*3^0=4_{10} }$ 和$\red{ 121_3 =1*3^2+2*3^1+1*3^0=16_{10} }$。

对于进制 $\red{10}$，同样有$\red{11_{10} * 11_{10} = 121_{10} }$。

这种情况下，应该输出 $\red{3}$。如果没有合适的进制，则输出 $\red{0}$。

输入格式

一行，包含三个整数$\red{p}$、$\red{q}$、$\red{r}$。 $\red{p}$、$\red{q}$、$\red{r}$的所有位都是数字， 并且$\red{1 ≤ p、q、r ≤ 1,000,000}$。

输出格式

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

样例

输入样例

6 9 42

输出样例

13