题目描述

通常我们会把一个十进制整数转换成某个进制下的表示。现在反过来：给定一个十进制整数 $N$ 和一个数字串 $S$，请判断是否存在一个进制 $B$，使得 $N$ 在 $B$ 进制下的表示正好等于 $S$。

例如，若 $S=111$，那么它在 $B$ 进制下表示的十进制值为：

如果这个值等于 $N$，则 $B$ 是一个可行进制。

请你找出最小的可行进制。如果不存在，输出 $-1$。

输入格式

一行，包含一个整数 $N$ 和一个数字串 $S$。

输出格式

输出一个整数，表示最小的可行进制；如果不存在，输出 $-1$。

样例 1

31 111

5

样例解释

$111$ 在 $5$ 进制下的值为：

所以答案为 $5$。

样例 2

10 101

3

数据范围

• $1 \le N \le 10^9$
• $S$ 只包含数字字符 0 到 9
• $1 \le |S| \le 10$
• 进制 $B$ 满足 $2 \le B \le 10^6$
• 保证 $S$ 的首位不为 0

提示

一个合法进制必须大于 $S$ 中出现的最大数字。