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:
20151122 20:50:46
Thanks @an_shuman777 for remind me.


an_shuman777:
20151121 19:44:35
I think the value of N should be greater than 1 not equal to 1. 
Added by:  bhardwaj_75 
Date:  20151119 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 