E. Bessie and Groups
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Farmer John has given his favorite cow, Bessie, an array $$$a$$$ of length $$$n$$$!

Bessie first splits the array into $$$n / k$$$ groups each of length $$$k$$$. Then, she performs two types of operations on the array, with all type $$$1$$$ operations coming before all type $$$2$$$ operations.

  1. Cyclically shift the groups to the left. Formally, if the array was originally $$$a_1, a_2, \ldots, a_n$$$, then after the operation it becomes $$$a_{k + 1}, a_{k + 2}, \ldots, a_n, a_1, \ldots, a_{k}$$$.
  2. Swap any two adjacent groups. Formally, if the array was originally $$$a_1, a_2, \ldots, a_n$$$, and Bessie decides to swap groups $$$i$$$ and $$$i + 1$$$ ($$$1 \le i \lt n / k$$$), then the array becomes $$$a_1, a_2, \ldots, a_{(i - 1)k}, a_{ik + 1}, \ldots, a_{(i + 1)k}, a_{(i - 1)k + 1}, \ldots, a_{ik}, a_{(i + 1)k + 1}, \ldots, a_n$$$.

    Note that you are not allowed to swap group $$$1$$$ and group $$$n / k$$$ as they are not adjacent.

Since Bessie is a very smart cow, she was able to sort the array using the minimum number of operations. Please determine how many operations Bessie used!

In other words, over all valid choices of $$$k$$$ and all valid sequences of operations with type $$$1$$$ operations coming before type $$$2$$$ operations, what is the minimum number of operations to sort the array? It can be shown that this is always possible.

Input

Each test consists of 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 2 \cdot 10^5)$$$ — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, ..., a_n$$$ $$$(0 \le a_i \le 10^9)$$$

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

Output

For each test case, output a single integer — the minimum number of operations required to sort the array $$$a$$$.

Example
Input
4
6
3 4 1 2 5 6
8
2 2 2 2 1 1 2 2
5
1 5 2 3 5
5
5 1 2 4 3
Output
1
1
2
2
Note

In the first test case, it's optimal to choose $$$k = 2$$$, then perform the second operation with the first and second groups.

In the second test case, it's optimal to choose $$$k = 2$$$, then perform the second operation with the third and fourth groups.

In the third test case, it's optimal to choose $$$k = 1$$$ and apply the second operation twice:

OperationArray
Initial$$$[1, 5, 2, 3, 5]$$$
Swap groups $$$2$$$ and $$$3$$$$$$[1, 2, 5, 3, 5]$$$
Swap groups $$$3$$$ and $$$4$$$$$$[1, 2, 3, 5, 5]$$$

In the fourth test case, it's optimal to choose $$$k = 1$$$ and apply one type $$$1$$$ operation followed by one type $$$2$$$ operation:

OperationArray
Initial$$$[5, 1, 2, 4, 3]$$$
Cyclic shift to the left$$$[1, 2, 4, 3, 5]$$$
Swap groups $$$3$$$ and $$$4$$$$$$[1, 2, 3, 4, 5]$$$

Note that swapping before shifting would have been invalid, because all type $$$1$$$ operations must come before all type $$$2$$$ operations.