1150 - 确定进制
Description

6∗9=42对于10进制来说是错误的,但是对于13进制来说是正确的。
即6(13)∗9(13)=42(13) ,而42(13)=4∗131+2∗130=54(10)。

现在编写一段程序,读入三个整数p、q和r,然后确定一个进制B(2<=B<=16)使得p∗q=r。如果B有很多选择,输出最小的一个。

Input

一行,包含三个整数p、q和r。p、q、r的 所有位都是数字,并且1 <= p、q、r <= 1000000

Output
一个整数B(使得p*q=r成立的最小B,如果没有合适的B输出0,且2<=B<=16)


Examples

Input

12 4 48

Output

9
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1