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$