Ehab's REAL Number Theory Problem

Description:

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".

Sample Input:

3
1 4 6

Sample Output:

1

Sample Input:

4
2 3 6 6

Sample Output:

2

Sample Input:

3
6 15 10

Sample Output:

3

Sample Input:

4
2 3 5 7

Sample 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.