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