Daddy of Tim and Bob may be a normal businessman in the eyes of the world, but secretly he owns the world’s longest garden (don't ask where, its highly confidential). But as he was very busy in his work, so he was not able to take care of his garden. So this Sunday he decided to spent his time in doing garden’s work. Over the years Daddy has planted n plants in his garden, of m different plant species numbered from 1 to m. His garden is very narrow and can be viewed as an infinite line, with each plant occupying a single point on that line.

Once he read in a magazine that each species of plant thrives at a different temperature, so he wants to arrange m - 1 borders that would divide the garden into m sections numbered from 1 to m from left to right with each section housing a single species. He is free to place the borders, but in the end all of the i-th species plants must reside in i-th section from the left.

Of course, it is not always possible to place the borders in such way, so Daddy needs to replant some of his plants. He can remove each plant from its position and place it anywhere in the garden (at any real coordinate) with no plant already in it. Since replanting is a lot of stress for the plants, as now you too know Daddy’s secret help him to find the minimum number of plants he has to replant to be able to place the borders.

Input

The first line of input contains number of test cases.
Each test case contains two space-separated integers n and m(1 ≤ n, m ≤ 5000, n ≥ m), the number of plants and the number of different species respectively. Each of the following n lines contain two space-separated numbers: one integer number s[i] (1 ≤ si ≤ m), and one real number x[i] (0 ≤ x[i] ≤ 6000), the species and position of the i-th plant. Each x[i] will contain no more than 6 digits after the decimal point. It is guaranteed that all x[i] are different; there is at least one plant of each species; the plants are given in order "from left to the right", that is in the ascending order of their xi coordinates (x[i] < x[i] + 1, 1 ≤ i < n).

Output

For each test case output the minimum number of plants to be replanted.

Constraints

As mentioned input part.

SAMPLE INPUT
2
5 5
5 0
4 1
3 2
2 3
1 4
3 3
2 0
1 1
3 2

SAMPLE OUTPUT
4
1

见题面

见题面