I. GCD Splicing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An array $$$c$$$ of length $$$n$$$ is good if it satisfies the following property:

  • For all $$$1 \lt i \le n$$$, there exists some $$$j \lt i$$$ such that $$$\gcd(c_i, c_j) \gt 1$$$.

We can measure the cost of some array $$$b$$$ of $$$n$$$ integers. In one operation, you can remove any good subsequence from the array. The cost of $$$b$$$ is the minimum number of operations to make the array empty.

You're given an array $$$a$$$ of length $$$n$$$. You want to minimise the cost of $$$a$$$ by performing the following action exactly once:

  • Choose positions $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$.
  • Perform a cyclic shift to the right on the subarray $$$a_{l \ldots r}$$$.

Please output the minimum cost after performing the following action exactly once on $$$a$$$.

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases. This is followed by descriptions of the test cases.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^5$$$).

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

Output

For each test case, output a single integer — the minimum cost of $$$a$$$ after performing the given action exactly once.

Example
Input
4
10
10 9 8 7 6 5 4 3 2 1
8
28 14 7 27 9 3 5 15
4
5 10 3 6
4
3 5 6 6
Output
3
2
1
2
Note

In the first sample, one optimal selection is to perform the action with $$$l = 2$$$ and $$$r = 5$$$. After performing the action, $$$a = [10, 6, 9, 8, 7, 5, 4, 3, 2, 1]$$$. We can show that the cost of this $$$a$$$ is equal to $$$3$$$:

  • In the first operation, remove the subsequence $$$[10, 6, 9, 8, 5, 4, 3, 2]$$$. Now $$$a = [7, 1]$$$.
  • In the second operation, remove the subsequence $$$[7]$$$.
  • In the third operation, remove the subsequence $$$[1]$$$.