Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

E. Ehab's REAL Number Theory Problem
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$ that has a special condition: every element in this array has at most 7 divisors. Find the length of the shortest non-empty subsequence of this array product of whose elements is a perfect square.

A sequence $$$a$$$ is a subsequence of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array $$$a$$$.

Output

Output the length of the shortest non-empty subsequence of $$$a$$$ product of whose elements is a perfect square. If there are several shortest subsequences, you can find any of them. If there's no such subsequence, print "-1".

Examples
Input
3
1 4 6
Output
1
Input
4
2 3 6 6
Output
2
Input
3
6 15 10
Output
3
Input
4
2 3 5 7
Output
-1
Note

In the first sample, you can choose a subsequence $$$[1]$$$.

In the second sample, you can choose a subsequence $$$[6, 6]$$$.

In the third sample, you can choose a subsequence $$$[6, 15, 10]$$$.

In the fourth sample, there is no such subsequence.