Bestie

题意翻译

小 C 有一个数列，她希望数列变得好看。定义所有元素 gcd 是 $1$ 的数列是好看的，同时定义一次操作是选择一个位置 $i(1\le i\le n)$，把 $a_i$ 修改为 $\gcd(a_i,i)$，这样一次操作的费用是 $n-i+1$。希望最小化把数列变好看的费用。

题目描述

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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) 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 $ .

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

0
1
2
2
1
3
3
0
1

说明

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 $ .

**题目大意：**

小 C 有一个包含 n 个整数的数组 a，她希望通过一系列操作使得数组变得“好看”，即数组中所有元素的的最大公约数（GCD）为 1。每次操作可以选取数组中的一个位置 i（1 ≤ i ≤ n），并将 a_i 修改为 a_i 和 i 的最大公约数，这样的操作需要花费 n-i+1 的代价。目标是找到最小化总代价的方案。

**输入输出格式：**

**输入格式：**
- 第一行包含一个整数 t（1 ≤ t ≤ 5000），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数 n（1 ≤ n ≤ 20），表示数组 a 的长度。
- 第二行包含 n 个整数 a_1, a_2, ..., a_n（1 ≤ a_i ≤ 10^9），表示数组的元素。

**输出格式：**
- 对于每个测试用例，输出一行，包含一个整数，表示使得数组中所有数的最大公约数变为 1 所需的最小总操作代价。

**输入输出样例：**

**输入样例 #1：**
```
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
```

**输出样例 #1：**
```
0
1
2
2
1
3
3
0
1
```

**说明：**

- 在第一个测试用例中，数组中所有数的最大公约数已经是 1，所以不需要进行任何操作。
- 在第二个测试用例中，选择 i = 1。操作后，a_1 = gcd(2, 1) = 1。这个操作的费用是 1。
- 在第三个测试用例中，选择 i = 1，之后数组 a 将变为 [1, 4]。这个数组的最大公约数是 1，总费用是 2。
- 在第四个测试用例中，选择 i = 2，之后数组 a 将变为 [3, 2, 9]。这个数组的最大公约数是 1，总费用是 2。
- 在第六个测试用例中，选择 i = 4 和 i = 5，之后数组 a 将变为 [120, 60, 80, 4, 5]。这个数组的最大公约数是 1，总费用是 3。**题目大意：** 小 C 有一个包含 n 个整数的数组 a，她希望通过一系列操作使得数组变得“好看”，即数组中所有元素的的最大公约数（GCD）为 1。每次操作可以选取数组中的一个位置 i（1 ≤ i ≤ n），并将 a_i 修改为 a_i 和 i 的最大公约数，这样的操作需要花费 n-i+1 的代价。目标是找到最小化总代价的方案。 **输入输出格式：** **输入格式：** - 第一行包含一个整数 t（1 ≤ t ≤ 5000），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数 n（1 ≤ n ≤ 20），表示数组 a 的长度。 - 第二行包含 n 个整数 a_1, a_2, ..., a_n（1 ≤ a_i ≤ 10^9），表示数组的元素。 **输出格式：** - 对于每个测试用例，输出一行，包含一个整数，表示使得数组中所有数的最大公约数变为 1 所需的最小总操作代价。 **输入输出样例：** **输入样例 #1：** ``` 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 ``` **输出样例 #1：** ``` 0 1 2 2 1 3 3 0 1 ``` **说明：** - 在第一个测试用例中，数组中所有数的最大公约数已经是 1，所以不需要进行任何操作。 - 在第二个测试用例中，选择 i = 1。操作后，a_1 = gcd(2, 1) = 1。这个操作的费用是 1。 - 在第三个测试用例中，选择 i = 1，之后数组 a 将变为 [1, 4]。这个数组的最大公约数是 1，总费用是 2。 - 在第四个测试用例中，选择 i = 2，之后数组 a 将变为 [3, 2, 9]。这个数组的最大公约数是 1，总费用是 2。 - 在第六个测试用例中，选择 i = 4 和 i = 5，之后数组 a 将变为 [120, 60, 80, 4, 5]。这个数组的最大公约数是 1，总费用是 3。