题目描述

表达式 $6×9=42$ 对于十进制来说是错误的，但是对于十三进制来说是正确的。即 $6(13)×9(13)=42(13)$，而 $42(13)=4×13^1+2×13^0=54(10)$。

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

如果 B 有很多选择，输出最小的一个。例如：$p=11,q=11,r=121$。则有 $11(3) ×11(3)=121(3)，11(10) ×11(10)=121(10)$。这种情况下，输出3。如果没有合适的进制，则输出0。

输入

一行，3 个 B 进制的正整数 $p、q、r$（$1 \le p, q, r \le 10^6$）。

输出

使得 $p×q=r$ 成立的最小进制 B，如果没有合适的进制，则输出0。

样例

6 9 42

13

Limitation

1s, 1024KiB for each test case.