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\)