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$$$.

Inverse Minimum Partition (Easy Version)

Examples