Start 2024-06-01 14:30:00

20240601下午基础1

End 2024-06-01 18:00:00
Contest is over.
Now 2026-11-19 00:33:23

D. 确定进制

Description

6\times9=42对十进制来说是错误的,但是对13进制来说却是正确的。即6_{(13)}\times9_{(13)}=42_{(13)},而42_{(13)}=4\times13+2\times1=54_{(10)}。

试编程读入3个整数p,q,r,然后确定一个进制B,使得p\times q=r。如果B有很多选择,则输出最小的那个进制。如果没有合适的进制,则输出0。

Input

一行给出三个整数p,q,r。

Output

一个整数:即令p\times q=r成立的最小的B。

Examples

Input

11 11 121

Output

3

Hint

2\leq B\leq 16,1\leq p,q,r\leq10^6


Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit