E. Ehab's REAL Number Theory Problemtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputOutput 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".ExamplesInput
3
1 4 6
Output
1Input
4
2 3 6 6
Output
2Input
3
6 15 10
Output
3Input
4
2 3 5 7
Output
-1NoteIn 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.
3
1 4 6

1
['brute force', 'dfs and similar', 'graphs', 'number theory', 'shortest paths', '*2600']