I hate every cheater ever but I specifically hate the ones from India WITH PASSION like they're not even trying to hide it, it's so blatant

10 minutes into the contest:

I hope Dominater069 looks to it.

Honestly, I think this is pretty good so I felt like sharing it.

Problem Statement

You are given a permutation $$$p_1,p_2,\ldots,p_n$$$.

An array $$$a_1,a_2,\ldots,a_m$$$ is called good if its indices can be partitioned into groups such that every group consists of indices $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$, where $$$k\geq 2$$$, and $$$a_{i_1} \lt a_{i_2} \lt \ldots \lt a_{i_k}$$$.

Every index must belong to exactly one group. The indices in a group do not have to be consecutive. The empty array is considered good.

Find the minimum number of elements you must delete from $$$p$$$ so that the remaining array is not good. Deleting elements does not change the relative order of the remaining elements.

If $$$p$$$ is already not good, the answer is $$$0$$$.

Constraints

• $$$1\leq t\leq 100$$$
• $$$1\leq n\leq 5000$$$
• $$$p$$$ is a permutation of $$$1,2,\ldots,n$$$.
• The sum of $$$n$$$ over all test cases is at most $$$5000$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 100$$$) — the number of test cases.

For each test case, the first line contains a single integer $$$n$$$ ($$$1\leq n\leq 5000$$$).

The second line contains $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ — a permutation of $$$1,2,\ldots,n$$$.

Output

For each test case, print a single integer — the minimum number of elements you have to delete so that the remaining array is not good.

Sample Input 1

2
6
2 1 4 3 6 5
5
1 2 3 4 5

Sample Output 1

3
4

Sample Input 2

3
1
1
4
3 2 1 4
4
1 2 4 3

Sample Output 2

0
0
1

78 minutes in and well...