Read problems statements in English, Mandarin Chinese and Russian as well.

Given an array A_{1},A_{2}...A_{N}, you have to print the size of the largest contiguous subarray such that
LCM of all integers in that subarray is equal to the product of all integers in that subarray.

Formally,
For a subarray A_{i},A_{i+1}...A_{j} where 1 ≤ i < j ≤ N to be valid: LCM(A_{i},A_{i+1}...A_{j}) should be equal to A_{i}A_{i+1}...*A_{j}. You have to print the size of the largest valid subarray.
If no subarray satisfies output -1.
Note:A single element is not considered a subarray according to definition in this problem.

------ Input ------

First line contains T, the number of testcases. Each testcase consists of N in one line followed by N integers in next line.

------ Output ------

For each testcase, print the required answer in one line.

------ Constraints ------

$1 ≤ T ≤ 50$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$

------ Example ------

Input:
3
2
7 2
4
2 2 3 4
3
2 2 4

Output:
2
2
-1

------ Explanation ------

Example case 1.LCM(2,7)=2*7. Therefore, subarray A_{1} to A_{2} satisfies.

Example case 2.The subarrays A_{2} to A_{3} and A_{3} to A_{4} are the maximum size possible.

Example case 3.No subarray will satisfy.

Warning: Use fast input/output. Large input files. Solutions may not pass in slower languages.

Update: Time limit for python=10s

见题面

见题面