说明

在"星火征途"的情报破译任务中，小红军发现了一份加密记录："6 × 9 = 42"。在十进制下这个算式是错误的，但在某种进制下却是正确的。 给定三个正整数p、q、r（每位数字均小于某个进制B），请你找出最小的进制B（2 ≤ B ≤ 40），使得 p × q = r 在B进制下成立。如果找不到这样的B，则输出0。

输入格式

输入共1行，三个正整数p、q、r，每位数字均小于B。用空格隔开。

输出格式

输出共1行，一个整数，表示最小的进制B；如果不存在则输出0。

6 9 42

13

提示

对于所有数据，p、q、r ≤ 1000000。思路：枚举B从2到40，将p、q、r按B进制转换为十进制后验证。注意：p、q、r的每一位数字都必须小于B。

来源

改编自PPT课件《7.10 进制转换》课后作业：确定进制（openjudge ch0201/1973）