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