Bridging Signals

Two rectangular blocks are placed side by side. Each block has ports numbered from 1 to N from top to bottom. Port i on the left block must be connected to port k_i on the right block.

Consider two different signals. If one signal starts above the other on the left block but ends below it on the right block, the two signals cross. Some crossing signals can be bridged so that they are lifted above the silicon surface, but as few signals as possible should be bridged.

Find the maximum number of signals that can be connected on the silicon surface without crossing each other.

The first line contains the number of test cases T.

For each test case, the first line contains the number of ports N. (1 ≤ N ≤ 40000)

The next N lines each contain one integer k_i. The i-th integer is the right-block port number that must be connected to port i on the left block. (1 ≤ k_i ≤ N)

For each test case, output one line containing the maximum number of signals that can be connected without crossing.