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 |