You are given an array \(A\) that contains \(N\) integer elements. The value \(A[i]\) of every element is such that the number of divisors of \(A[i]\) is at most 7.

Find the length of the smallest non-empty subsequence of this array such that the product of elements in the subsequence is a perfect square. If no such subsequence exists, then print -1.

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

Input format

• The first line contains an integer \(N\) denoting the number of elements in the array.
• The second line contains \(N\) space-separated integers denoting array \(A\).

Output format

Print an integer, denoting the length of the smallest non-empty subsequence of the array that satisfies the mentioned conditions.

Constraints

\(1 \le N \le 10^5 \\ 1 \le A[i] \le 10^6\)