DB001 - DB & GCD


 

  Db hates mathematics a lot.Oneday his mathematics teacher gives him a assignment.So he is asking for help to complete his assignment.Help Db as he is busy at november challenge at Codechef.
  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.

 

 

 

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