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
Output format
Print an integer, denoting the length of the smallest non-empty subsequence of the array that satisfies the mentioned conditions.
Constraints
1≤N≤1051≤A[i]≤106