题目描述

给定一个由 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 组成的数组 $a$。朋友们要求你将数组中所有数的最大公约数（GCD）变为 $1$。每次操作，你可以进行如下操作：

• 选择数组中的任意一个下标 $1 \leq i \leq n$；
• 令 $a_i = \gcd(a_i, i)$，其中 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。该操作的代价为 $n - i + 1$。

你需要求出，为了使整个数组的最大公约数变为 $1$，所需操作的最小总代价。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 20$），表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组的元素。

输出格式

对于每组测试用例，输出一个整数，表示将数组所有数的最大公约数变为 $1$ 所需的最小总代价。

可以证明总是存在一种操作方案使得最终最大公约数为 $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$。

由 ChatGPT 4.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

0
1
2
2
1
3
3
0
1