You are given a sequence of numbers. You can change any number from the sequence to any other number of your choice. Your task is to minimize the number of numbers changed in order to make the sequence strictly increasing.

Input:

The first line of input is an integer T(T <= 5), the number of test cases. Each test case contains 2 lines.
The first line of the test case contains an integer (0 < N <= 10^5), i.e. the number of elements in the sequence.
The second line contains N positive integers, no larger than 2*10^9, which forms the sequence.

Output:

For each test case output the minimal number of elements you must change in the given sequence to get the desired one.