Hide

Problem M
Unown Code

/problems/unowncode/file/statement/en/img-0001.png
Unown Digits

Professor Rowan has been researching a group of Unown in the Solaceon Ruins who have come up with a secret code. Each Unown is shaped like a digit, and they have grouped together to form $N$ numbers ($a_1, \ldots , a_ N$). Their code is the smallest integer $c > 1$ such that when each of the numbers $a_ i$ are raised to the $c$-th power, the result ends with the digits of $a_ i$. For example, if the numbers were $3$ and $25$, the secret code would be $5$, as $3^5 = 243$, which ends with $3$, and $25^5 = 9\, 765\, 625$, which ends with $25$.

Write a program to help Professor Rowan figure out the secret code.

Input

The first line of input contains a single integer $N$ ($1 \leq N \leq 10^6$), the number of groups of Unown.

The second line contains $N$ space-separated integers $a_1, \ldots , a_ N$ ($1 \leq a_ i \leq 10^9$) representing the numbers formed by each group of Unown. It is guaranteed that none of the numbers contain a leading zero.

Output

Output a single line containing the secret code, or $-1$ if no such code exists.

Sample Input 1 Sample Output 1
2
3 25
5
Sample Input 2 Sample Output 2
1
5
2
Sample Input 3 Sample Output 3
2
5 10
-1

Please log in to submit a solution to this problem

Log in