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.
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)
For every test case print maximum length of a contiguous subsequence if such type of subsequence does not exist,print -1.