DB001 - DB & GCD


Db hates mathematics a lot. One day his mathematics teacher gives him a assignment. So he is asking for help to complete his assignment. Help Db as he is busy at SPOJ. The statement of assignment question is:

You are given an array A of integer of size N. Now your task is to find the maximum length of a contiguous subsequence among all beautiful subsequences. A beautiful subsequence is defined as a subsequence with GCD 1.

Note: GCD of subsequence means GCD of all element present in subsequence.

Input

First line of input contains 1 <= T <= 100 number of test cases.

The first line of each test cases contains a number N (2 <= N <= 100000) Next line contains the elements of array A (1<= A[i] <= 1e9)

Output

For every test case print maximum length of a contiguous subsequence if such type of subsequence does not exist, print -1.

Example

Input:
2
2
2 4
2
1 1

Output:
-1
2

hide comments
DIWAKAR BHARDWAJ: 2015-11-22 20:50:46

Thanks @an_shuman777 for remind me.

an_shuman777: 2015-11-21 19:44:35

I think the value of N should be greater than 1 not equal to 1.


Added by:bhardwaj_75
Date:2015-11-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY