#1031 사다리

84  1 s   128 MB  

Description

야식을 걸고 세 남자의 운명을 결정하기 위한 사다리게임이 시작되려고 한다. 여기서 걸린 사람이 군말 없이 야식을 쏴야 한다.

 

김고리는 군대에 가기 직전에 야식을 쏘게 되면 왠지 억울할 것 같아 사다리게임에서 자신이 전적으로 줄을 그으려고한다. 절대로 걸리기 싫은 김고리는 결과를 미리 정해놓고, 이에 맞게 결과가 결정되도록 하고자 하는데, 재촉하는 친구들 때문에 최대한 빨리 그어야 하므로, 선긋기 횟수를 최소로 하려 한다.

결과에 대해 김고리가 그어야 하는 최소의 선의 횟수를 구하는 프로그램을 출력하라.

 

Input

입력은 T개의 테스트 케이스로 이뤄진다. T는 10이하의 정수다.

입력의 첫 줄에는 테스트 케이스 개수 T가 주어진다. 다음줄 부터 테스트 케이스가 입력된다.

각 테스트케이스의 첫줄에는 사람의 수 N이 입력되며, 다음줄에는 N개의 정수가 입력된다. N은 1이상 100이하의 정수다.

각 숫자는 사람의 번호를 뜻하며, 김고리가 원하는 결과를 뜻한다. 만약 "1 4 2 3"이면 첫번째 결과에는 1번이, 2번째 결과에는 4번이, 3번째 결과에는 2번이, 마지막에는 3번이 당첨되어야 한다는 것이다. 사람의 번호가 겹치는 경우는 존재하지 않으며, 1이상 N이하의 번호가 한번씩 입력된다.

Output

각 테스트 케이스에 대해 그어야 하는 최소 사다리의 수를 입력된 테스트 케이스의 순서대로 한줄에 하나씩 출력한다.

Sample Input

Sample Output

2
2
2 1
4
1 2 3 4
1
0