Problem G
Unown Code
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 |
