길동이는 퍼즐 게임을 만들고 있다. 게임에는 번부터 번까지 번호가 붙은 개의 발판이 있다. 플레이어의 캐릭터는 처음에 번 발판에 있으며, 번 발판에 도착하면 게임에서 승리한다.
번 발판에는 정수 가 적혀 있다. 캐릭터가 번 발판에 있다면, 플레이어는
를 만족하는 임의의 번 발판으로 캐릭터를 이동시킬 수 있다. 번이 아닌 발판에 도착했는데 그 발판에 적힌 수가 이면 게임에서 패배한다.
길동이는 게임을 더 어렵게 만들기 위해 일부 발판에 적힌 수를 으로 바꾸려고 한다. 그 결과, 번 발판에서 출발하여 번 발판에 도착하는 경로가 정확히 하나만 남아야 한다. 두 경로에서 방문하는 발판의 집합이 다르면 서로 다른 경로로 센다.
수를 바꾸는 발판 개수의 최솟값을 구하여라. 이미 조건을 만족한다면 아무 발판도 바꾸지 않아도 된다.
첫째 줄에 테스트 케이스의 수 가 주어진다.
각 테스트 케이스는 두 줄로 이루어진다.
첫째 줄에 발판의 수 이 주어진다.
둘째 줄에 개의 정수 이 공백으로 구분되어 주어진다.
각 테스트 케이스마다, 승리하는 경로가 정확히 하나만 남도록 하기 위해 적힌 수를 으로 바꾸어야 하는 발판 개수의 최솟값을 한 줄에 출력한다.
첫 번째 테스트 케이스에서는 처음부터 승리하는 경로가 하나뿐이므로 답은 이다.
두 번째 테스트 케이스에서는 를 으로 바꿀 수 있다. 그러면 수열은 이 되고, 승리하는 경로는 하나만 남는다.
세 번째 테스트 케이스에서는 을 으로 바꿀 수 있다. 그러면 승리하는 경로는 하나만 남는다.
