You are given an array \(a\) of \(n\) positive integers. In one operation, you can take two adjacent elements and replace both of them with the greatest common divisor of those integers. You need to perform the minimum number of operations to make at least one element as small as possible.

The first line contains a single integer \(t\) \((1 \leq t \leq 10^5)\) — the number of test cases.
The first line of each test case contains a single integer \(n\) \((1 \leq n \leq 10^5)\) — the size of the array.
The second line of each test case contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq 10^9)\) — the array \(a\).
It is guaranteed that the sum of \(n\) over all test cases doesn't exceed \(2 \cdot 10^5\).

For each test case, print a single integer — the minimum number of operations to be performed to make at least one element as small as possible.

Input copy	Output copy
2 5 4 5 6 2 3 5 2 4 6 3 6	1 2