#P4969. 确定进制

确定进制

确定进制

题目描述

在 BB 进制中,把数字串 pp、qq、rr 分别当作 BB 进制数,记它们的值为 pB,qB,rBp_B,q_B,r_B。

求最小的 BB(2≤B≤402 \le B \le 40),使得 pB×qB=rBp_B \times q_B = r_B 成立,并且 p,q,rp,q,r 的每一位数字都小于 BB。若不存在这样的 BB,输出 00。

例如,十三进制下 6×9=426 \times 9 = 42,因为十进制下 6×9=546 \times 9=54,而 4213=4×13+2=5442_{13}=4 \times 13+2=54。

输入格式

一行,包含三个整数 p,q,rp,q,r,相邻两个数之间用一个空格隔开。

输出格式

输出一个整数,即满足条件的最小进制 BB;若不存在,输出 00。

数据范围与约定

1≤p,q,r≤10000001 \le p,q,r \le 1000000,p,q,rp,q,r 的所有位都是十进制数字。

样例输入

6 9 42

样例输出

13

说明

测试数据为课程配套独立生成。