브리징 시그널

두 개의 직사각형 블록이 나란히 있고, 각 블록에는 위에서 아래로 1번부터 N번까지 번호가 붙은 포트가 있다. 왼쪽 블록의 i번 포트는 오른쪽 블록의 k_i번 포트와 연결되어야 한다.

서로 다른 두 시그널을 생각해 보자. 왼쪽 블록에서는 한 시그널이 다른 시그널보다 위에 있는데, 오른쪽 블록에서는 그 순서가 뒤바뀐다면 두 시그널은 교차한다. 교차하는 시그널 중 일부는 브리징하여 실리콘 표면 위로 띄울 수 있지만, 브리징해야 하는 시그널 수는 가능하면 적어야 한다.

실리콘 표면 위에서 서로 교차하지 않고 그대로 연결할 수 있는 시그널의 최대 개수를 구하시오.

첫 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 포트의 개수 N이 주어진다. (1 ≤ N ≤ 40000)

다음 N개의 줄에는 정수 k_i가 한 줄에 하나씩 주어진다. i번째 정수는 왼쪽 블록의 i번 포트가 연결되어야 하는 오른쪽 블록의 포트 번호이다. (1 ≤ k_i ≤ N)

각 테스트 케이스마다 서로 교차하지 않고 연결할 수 있는 시그널의 최대 개수를 한 줄에 하나씩 출력한다.