Divide and Conquer

Description:

Input:

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — representing the array $$$a$$$.

Do note that the sum of $$$n$$$ over all test cases is not bounded.

Output:

For each test case, output the minimum number of operations needed to make $$$a$$$ good.

Sample Input:

4
4
1 1 1 1
2
7 4
3
1 2 4
1
15

Sample Output:

0
2
1
4

Note:

In the first test case, array $$$a$$$ is already good.

In the second test case, we can perform on index $$$2$$$ twice. After the first operation, array $$$a$$$ becomes $$$[7,2]$$$. After performing on index $$$2$$$ again, $$$a$$$ becomes $$$[7,1]$$$, which is good. It can be proved that it is not possible to make $$$a$$$ good in less number of operations.

In the third test case, $$$a$$$ becomes $$$[0,2,4]$$$ if we perform the operation on index $$$1$$$ once. As $$$[0,2,4]$$$ is good, answer is $$$1$$$.

In the fourth test case, we need to perform the operation on index $$$1$$$ four times. After all operations, $$$a$$$ becomes $$$[0]$$$. It can be proved that it is not possible to make $$$a$$$ good in less number of operations.