It was a normal weekday evening in Magnitogorsk. Phil and Cosmos were returning home by car after a hard shift. Here Kosmos remembered that Bely had given him a task that he had safely forgotten to complete. To protect Kosmos from the wrath of Sasha Bely, help him complete the task.
Given n integers a
1,a
2,...,a
n. It is required to make the greatest common divisor (GCD) of all numbers in the array equal to 1. In one operation, you can do the following:
Choose an arbitrary index in array 1 <= i <= n;
Make a
i = gcd(a
i,i). The cost of such an operation is n − i + 1.
It is required to find the minimum total cost of operations that will need to be done so that the GCD of the array numbers becomes equal to 1.
Input
Each test consists of several sets of input data. The first line contains an integer t (1 <= t <= 5000) — the number of test cases. The following is a description of the input data sets.
The first line of each test case contains a single integer n (1 <= n <= 20) — the length of the array.
The second line of each test case contains n integers a
1,a
2,...,a
n (1 <= a< sub>i <= 10
9) — array elements.
Imprint
For each test case print a single integer — the minimum total cost of operations that will need to be done so that the GCD of the array numbers becomes equal to 1.
Examples
| # |
Input |
Output |
| 1 |
7
1
1
1
2
2
24
3
3 6 9
4
5 10 15 20
5
120 60 80 40 80
6
150 90 180 120 60 30
| 0
1
2
2
1
3
3 |
Remark
In the first test case, the GCD of the entire array is already equal to 1, so there is no need to apply the operation.
In the second test case, choose i = 1. After this operation, a1 = gcd(2,1) = 1. The cost of this operation was 1.
In the third test case, you will need to choose i = 1, after which 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 need to choose i = 2, after which 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 choose i = 3, after which the array a will be equal to [120,60,1,40,80]. The gcd of this array is 1 and the total cost is 3.