Bob is a brilliant student in the class and hence his teacher assigned him a problem. He has been given an array \(A\) of \(N\) positive integers and has been asked to make the magic count of the whole array equal to \(1\) by performing the below operation some number of times. The magic count of the array is the greatest common divisor (GCD) of all numbers in it.
Help Bob in finding the minimum total cost to make the magic count of all the whole array equal to \(1\).
Note: Consider 1-based array indexing for the above problem.
Input Format:
Output Format:
For each test case, print the minimum total cost to make the magic count of the whole array equal to \(1\).
Constraints:
\(1<= T <=10\)
\(1 <= N <= 10^5\)
\(0 <= A[i] <= 10^9\)
For test case 1:
The magic count of the whole array is already \(1\) hence the cost needed will be \(0\).
For test case 2:
If we apply the operation on the \(3^{rd}\) index the updated array will be \([2,3,1]\) and its magic count will be \(1\), Hence, the minimum possible cost that can be obtained is \(1\).