C. Prime Dominion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$.

A subarray is called valid if the greatest common divisor (GCD) of all its elements is a prime number.

Your task is to determine the maximum possible length of any valid subarray.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 2 \cdot 10^5$$$) — the number of test cases.

Then $$$T$$$ test cases follow. Each test case consists of two lines:

The first line of each test case contains a single integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — the size of the array.

The second line contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the elements of the array.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the length of the longest valid subarray. If there is no such subarray, print $$$-1$$$.

Examples
Input
1
5
2 4 6 9 3
Output
3
Input
3
2
6 12
6
6 9 15 21 27 33
5
5 10 15 20 25
Output
-1
6
5
Note

Explanation:

Test case 1:

The array is $$$[2, 4, 6, 9, 3]$$$. - The subarray $$$[6, 9, 3]$$$ has GCD $$$3$$$, which is a prime number. Its length is $$$3$$$, which is the maximum possible length among all valid subarrays.

Test case 2:

1. Array: $$$[6, 12]$$$ — GCD of any subarray is not prime. So the answer is $$$-1$$$. 2. Array: $$$[6, 9, 15, 21, 27, 33]$$$ — the entire array has GCD $$$3$$$, which is prime. Maximum length is $$$6$$$. 3. Array: $$$[5, 10, 15, 20, 25]$$$ — the entire array has GCD $$$5$$$, which is prime. Maximum length is $$$5$$$.