未知图腾数字

罗温教授一直在研究随意遗迹中的一群未知图腾，它们想出了一个密码。每个未知图腾的形状都像一个数字，它们组合在一起形成了 $N$ 个数 $(a_1, \dots, a_N)$。它们的密码是最小的整数 $c > 1$，使得对于每个数 $a_i$，$a_i^c$ 的十进制表示都以 $a_i$ 结尾。例如，如果这些数是 $3$ 和 $25$，那么密码将是 $5$，因为 $3^5 = 243$（以 $3$ 结尾），且 $25^5 = 9\,765\,625$（以 $25$ 结尾）。

请编写一个程序，帮助罗温教授找出这个密码。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 10^6$），表示未知图腾组的数量。

第二行包含 $N$ 个空格分隔的整数 $a_1, \dots, a_N$（$1 \le a_i \le 10^9$），表示每组未知图腾所组成的数。保证这些数都不包含前导零。

输出格式

输出一行，包含该密码；如果不存在这样的密码，则输出 $-1$。

样例

输入样例 1

2
3 25

输出样例 1

5

输入样例 2

1
5

输出样例 2

2

输入样例 3

2
5 10

输出样例 3

-1