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 ≤ 10⁶), the number of crossings. Then N integers a₁, …, a_N follow, where a_i is the crossing next to the crossing i that when going towards the outside. The integer a_i is zero if a_i is directly connected to the outside.

The depth of the tree is at most 10⁴.

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