Even Harder (Even Harder)

길동이는 퍼즐 게임을 만들고 있다. 게임에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 발판이 있다. 플레이어의 캐릭터는 처음에 $1$번 발판에 있으며, $n$번 발판에 도착하면 게임에서 승리한다.

$i$번 발판에는 정수 $a_i$가 적혀 있다. 캐릭터가 $i$번 발판에 있다면, 플레이어는

를 만족하는 임의의 $j$번 발판으로 캐릭터를 이동시킬 수 있다. $n$번이 아닌 발판에 도착했는데 그 발판에 적힌 수가 $0$이면 게임에서 패배한다.

길동이는 게임을 더 어렵게 만들기 위해 일부 발판에 적힌 수를 $0$으로 바꾸려고 한다. 그 결과, $1$번 발판에서 출발하여 $n$번 발판에 도착하는 경로가 정확히 하나만 남아야 한다. 두 경로에서 방문하는 발판의 집합이 다르면 서로 다른 경로로 센다.

수를 바꾸는 발판 개수의 최솟값을 구하여라. 이미 조건을 만족한다면 아무 발판도 바꾸지 않아도 된다.

첫째 줄에 테스트 케이스의 수 $t$가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다.

• 첫째 줄에 발판의 수 $n$이 주어진다.

• 둘째 줄에 $n$개의 정수 $a_1,a_2,\ldots,a_n$이 공백으로 구분되어 주어진다.

각 테스트 케이스마다, 승리하는 경로가 정확히 하나만 남도록 하기 위해 적힌 수를 $0$으로 바꾸어야 하는 발판 개수의 최솟값을 한 줄에 출력한다.

• $1\le t\le 250\,000$
• $2\le n\le 500\,000$
• $0\le a_i\le$ ()