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.

见题面

见题面