MORIA3 - Watching over the Mines of Moria


Soon after they settled in the Mines of Moria, the Orcs wanted to install a video surveillance system. The Mines of Moria are simple: they are straigh-line tunnels connecting crossings. There is at most one path to go from one crossing to another.

The Orcs want to install cameras at crossings. A camera can watch over the crossing where it sits, but also the crossings next to it, that is separated by one tunnel.

Find the smallest number of cameras that the Orcs need to watch over all the crossings.

We don’t know precisely, but here is what the Mines of Moria may look like. The crossings are numbered from 1 to 10. The node 0 represents the outside world and need not be covered by a camera. In this example, it is possible to watch over all the crossings with only three cameras.

Input

The inputs that with an integer T (1 ≤ T ≤ 1000), the number of test cases. Then follows T lines, one for each test case.

Each test case start with an integer N (1 ≤ N ≤ 2×106), the number of crossings. Then N integers a1, …, aN follow, where ai is the crossing next to the crossing i that when going towards the outside. The integer ai is zero if ai is directly connected to the outside.

The depth of the tree is at most 104.

Output

For each test case, output the cardinality of the smallest subset S of the crossings such that each crossing is in S or adjacent to a crossing in S.

Example

input:
3
3 0 0 0
3 0 1 2
10 2 0 2 5 8 5 8 0 7 9

output:
3
1
3

hide comments
anonymous: 2021-08-09 17:53:34

Input constraints appear to be inconsistent with provided test cases.

[pierre: how so? I see no issue.]

See submission 28300406. I had assertions checking input ranges. They failed.

[pierre: oops, my bad... one test case has 1010101 nodes... Thanks]

Thanks for checking!

Last edit: 2021-11-19 11:15:36
bogumil_lat: 2021-06-09 14:46:56

but can a camera be placed in a 0 node or is it forbidden?

[pierre: no, no camera at 0, as indicated by the example input "3 0 0 0"]

Last edit: 2021-06-11 10:31:30

Added by:pierre
Date:2021-05-27
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All