This is the easy version of the problem. The difference between the versions is that in this version, you are only asked to find $f(a)$. You can hack only if you solved all versions of this problem.

For some sequence $b$ of $k$ positive integers, the cost of the sequence is defined as follows$^{\text{∗}}$:

$$\mathtt{cost}(b)=\left\lceil{\frac{b_k}{\min(b_1,b_2,\ldots,b_k)}}\right\rceil$$

Assume that you partition a sequence $c$ into one or more sequences, so that the sequences become $c$ when concatenated. For example, when the sequence $c$ is $[3,1,4,1,5]$, a few valid ways to partition the sequence are $[[3,1],[4,1,5]]$, $[[3],[1,4,1],[5]]$, $[[3,1,4,1,5]]$. On the other hand, $[[3,1],[1,5]]$ and $[[3,4,1],[1,5]]$ are not valid ways to partition the sequence.

For a partition of a sequence $c$ of positive integers, the total cost of the partition is defined as the sum of the costs of each sequence in the partition. Then, let us define $f(c)$ as the minimum total cost to partition the sequence $c$.

Given a sequence $a$ of $n$ positive integers, you must compute the value of $f(a)$.

$^{\text{∗}}$Given a real value $x$, $\left\lceil{x}\right\rceil$ is defined as the smallest integer no less than $x$. For example, the value of $\left\lceil{3.14}\right\rceil$ is $4$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 4\cdot 10^5$).

The second line of each test case contains $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{18}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $4\cdot 10^5$.

Output

For each test case, output the answer to the problem on a separate line.

Note

For the first test case, the partition $[[3,1,4,1],[5]]$ gives a total cost of $1+1=2$.

For the second test case, the partition $[[9,2,6,5,3],[5,8,9,7,9]]$ gives a total cost of $2+2=4$.

For the third test case, the partition $[[1],[2,3,4],[5,6,7,8]]$ gives a total cost of $1+2+2=5$.

For the fourth test case, the partition $[[1],[1\,000\,000\,000\,000\,000\,000]]$ gives a total cost of $1+1=2$.