Bestie
Contest: Codeforces Round 830 (Div. 2)
Difficulty rating: 1000
Tags: brute force, combinatorics, constructive algorithms, implementation, math, number theory

You are given an array $$$a$$$ consisting of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Friends asked you to make the greatest common divisor (GCD) of all numbers in the array equal to $$$1$$$. In one operation, you can do the following:

- Select an arbitrary index in the array $$$1 \leq i \leq n$$$;
- Make $$$a_i = \gcd(a_i, i)$$$, where $$$\gcd(x, y)$$$ denotes the GCD of integers $$$x$$$ and $$$y$$$. The cost of such an operation is $$$n - i + 1$$$.

You need to find the minimum total cost of operations we need to perform so that the GCD of the all array numbers becomes equal to $$$1$$$.

Input format:
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5\,000$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 20$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.

Output format:
For each test case, output a single integer — the minimum total cost of operations that will need to be performed so that the GCD of all numbers in the array becomes equal to $$$1$$$.

We can show that it's always possible to do so.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the GCD of the entire array is already equal to $$$1$$$, so there is no need to perform operations.

In the second test case, select $$$i = 1$$$. After this operation, $$$a_1 = \gcd(2, 1) = 1$$$. The cost of this operation is $$$1$$$.

In the third test case, you can select $$$i = 1$$$, after that the array $$$a$$$ will be equal to $$$[1, 4]$$$. The GCD of this array is $$$1$$$, and the total cost is $$$2$$$.

In the fourth test case, you can select $$$i = 2$$$, after that the array $$$a$$$ will be equal to $$$[3, 2, 9]$$$. The GCD of this array is $$$1$$$, and the total cost is $$$2$$$.

In the sixth test case, you can select $$$i = 4$$$ and $$$i = 5$$$, after that the array $$$a$$$ will be equal to $$$[120, 60, 80, 4, 5]$$$. The GCD of this array is $$$1$$$, and the total cost is $$$3$$$.

Example input:
9
1
1
1
2
2
2 4
3
3 6 9
4
5 10 15 20
5
120 60 80 40 80
6
150 90 180 120 60 30
6
2 4 6 9 12 18
6
30 60 90 120 125 125

Example output:
0
1
2
2
1
3
3
0
1

Editorial:
Let's make an important observation: $$$\gcd(n - 1, n) = 1$$$ for any value of $$$n$$$. Moreover, choosing $$$i = n - 1$$$ and $$$i = n$$$ are the cheapest operations. From this we can conclude that the answer is $$$\leq 3$$$.
Let $$$g$$$ be the $$$\gcd$$$ of all numbers in the array. Then we have the following cases:
• If $$$g = 1$$$, then the operation can be omitted and the answer is $$$0$$$,
• Otherwise, let's try the cheapest operation $$$i = n$$$. If $$$\gcd(g, n) = 1$$$, then the answer is $$$1$$$.
• Otherwise, let's try the next cheapest operation, ie $$$i = n - 1$$$. If $$$\gcd(g, n - 1) = 1$$$, then the answer is $$$2$$$.
• Otherwise, the answer is $$$3$$$, since $$$\gcd(g, n - 1, n) = 1$$$.