You are given an array $A$ of $N$ distinct integers, your task is to sort the given array using the below operation.

•  Choose any element, take it out of the array without changing the order of other elements, and put it back either in front or back.

Your task is to print the minimum number of operations to achieve this.

Input format

• The first line contains an integer denoting the number of test cases $T$. 
• The first line of each test case contains an integer $N$ denoting the number of elements in array $A$.
• The second line of each test case contains $N$ space-separated integers of array $A$.

Output format

Print $T$ lines. For each test case:

• Print a single line indicating the minimum number of operations to be performed.

Constraints

$1 \leq T \leq 20000$

$1 \leq N \leq 200000$

$1 \leq A_i \leq 10^9 \forall i \in [1,N]$

All $A_i$ are distinct.

The sum of N over all test cases does not exceed 200000.