Subarray LCM

All submissions for this problem are available.
Read problems statements in English, Mandarin Chinese and Russian as well.
Given an array A_{1},A_{2}...A_{N}, you have to print the size of the largest contiguous subarray such that
LCM of all integers in that subarray is equal to the product of all integers in that subarray.
Formally,
For a subarray A_{i},A_{i+1}...A_{j} where 1 ≤ i < j ≤ N to be valid: LCM(A_{i},A_{i+1}...A_{j}) should be equal to A_{i}*A_{i+1}*...*A_{j}. You have to print the size of the largest valid subarray.
If no subarray satisfies output 1.
Note:A single element is not considered a subarray according to definition in this problem.
Input
First line contains T, the number of testcases. Each testcase consists of N in one line followed by N integers in next line.
Output
For each testcase, print the required answer in one line.
Constraints
 1 ≤ T ≤ 50
 2 ≤ N ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{6}
Example
Input: 3 2 7 2 4 2 2 3 4 3 2 2 4 Output: 2 2 1
Explanation
Example case 1.LCM(2,7)=2*7. Therefore, subarray A_{1} to A_{2} satisfies.
Example case 2.The subarrays A_{2} to A_{3} and A_{3} to A_{4} are the maximum size possible.
Example case 3.No subarray will satisfy.
Warning: Use fast input/output. Large input files. Solutions may not pass in slower languages.
Update: Time limit for python=10s
Author:  darkshadows 
Editorial  http://discuss.codechef.com/problems/SUBLCM 
Tags  cook50 darkshadows dp lcm math medium 
Date Added:  23062014 
Time Limit:  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
plz help getting WA and cant
i got nzec error in pythan of
Can some please mention some
Man, this one is tricky.