사다리

상덕이는 점심 메뉴를 정하기 위해 사다리 게임을 하려 한다. 희원이는 원하는 결과가 나오도록 사다리에 가로줄을 그리려고 한다.

사다리에는 N개의 세로줄이 있고, 각 가로줄은 인접한 두 세로줄을 연결한다. 위에서 아래로 내려가며 가로줄을 만나면 반대쪽 세로줄로 이동한다. 같은 높이에 그려진 가로줄은 없다고 하자.

각 도착점에 어떤 시작점이 도착해야 하는지가 주어진다. 원하는 결과를 만들기 위해 필요한 가로줄 개수의 최솟값을 구하시오.

입력은 T개의 테스트 데이터로 구성된다. 첫 줄에는 테스트 데이터의 개수 T가 주어진다.

각 테스트 데이터는 두 줄로 구성된다. 첫 줄에는 사다리 세로줄의 개수 N이 주어진다. 둘째 줄에는 N개의 정수 a_1, a_2, ..., a_N이 공백으로 구분되어 주어진다. a_i는 i번 도착점에 도착하는 시작점의 번호이다.

각 시작점은 정확히 하나의 도착점에 도착하며, N은 1,000 이하의 자연수이다.

각 테스트 데이터마다 원하는 결과를 만들기 위해 필요한 가로줄의 최소 개수를 한 줄에 출력한다.