Description:
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 Format:
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 Format:
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".
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.