Solve the programming task below in a Python markdown code block.
You are given an array A of N positive integers. 

In one operation, you can do the following:
Choose an index i (1 ≤ i ≤ N), and change the value of A_{i} to either (A_{i})^2 or \lfloor \sqrt{A_{i}} \rfloor.

Find the minimum number of operations required, such that, for the final array A:
A is sorted in non-decreasing order;
A_{N} ≤ 10^{18}.

NOTE: The elements of the array might not fit in a 32-bit integer.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input:
- The first line of each test case contains N - the size of the array.
- The next line contains N integers, A_{1}, A_{2}, A_{3}, \ldots, A_{N} - the elements of the array.

------ Output Format ------ 

For each test case, output on a new line, the minimum number of operations required.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{18}$
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
3
4
1 3 9 9
4
1 9 3 9
3
4 2 1

----- Sample Output 1 ------ 
0
1
3

----- explanation 1 ------ 
Test case $1$: The array is already sorted, no operation is required.

Test case $2$: Using one operation, we can change $A_{2}$ to $\lfloor \sqrt{A_{2}}\rfloor = 3$. The final array is $A = [1, 3, 3, 9]$ which is sorted in non-decreasing order.

Test case $3$: We make the following operations:
- Change $A_{2}$ to $\lfloor \sqrt{A_{2}}\rfloor = 1$.
- Change $A_{1}$ to $\lfloor \sqrt{A_{1}}\rfloor = 2$.
- Change $A_{1}$ to $\lfloor \sqrt{A_{1}}\rfloor = 1$.

The final array is $A = [1, 1, 1]$ which is sorted in non-decreasing order.