B"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: 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 <= q t <= q 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 <= q n <= q 20 ) -- the length of the array. The second line of each test case contains n integers a_1, a_2, ldots, a_n ( 1 <= q a_i <= q 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. 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 . "...