The King of Thuvax decided to conquer the neighbouring country of Silicon Valley. In order to conquer  a country, he has to successfully invade every city in the country. But he always doesn't get into action unless he plans it properly. He knows that severing a city's communications with all other cities before invading it is the only way to conquer it. He has the information regarding how the cities communicate with each other through his spy. The spy has lived in Silicon Valley right from the time when it was a single city, much before its development into a country. He gives information about how every new city established communication links with other cities. The spy's information is represented as below.

Every city can establish its communications with the help of only one other city. It can do it in one of the three ways.

Type 1 - It can establish a single communication link with another city 'c'.

Type 2 - It can establish communication links with all cities that communicate with another city 'c', but it can't have a communication link with 'c'.

Type 3 - It can establish communication links with all cities that communicate with another city 'c' and with 'c' also.

All communication links are two-way. Having this information, he finds out that it is not possible for him to invade Silicon Valley in a fair way. So he hires a terrorist gang to bomb some cities and destroy them so that he can invade the country successfully. But the terrorists demanded a huge amount of money for bombing a city. Help the King to find out the minimum number of cities that should be bombed so that he can conquer the country of Silicon Valley successfully.

Input

The first line consists of number of test cases t (1 <= t <= 10)

The first line of each test case consists of the number of cities n (1 <= n <= 10^4) in Silicon Valley.

Each of the next n-1 lines consists of two integers x and c.

The ith (1 <= i <= n-1) line represents that city i+1 establishes a type 'x' communication link with the help of the city 'c' (1 <= c <= i). (The country initially contains city 1 alone.)

Output

Output one line for each test case containing the minimum number of cities that should be bombed so that the King can conquer the country.

Sample

Input
2
2
1 1
3
1 1
3 1

Output
1
2

Explanation

1. Here city 2 has communication links with city 1. So to conquer the country, The King has to bomb one of these cities and then invade the remaining city.
2. Here city 2 has communication links with city 1 and city 3 establishes communication links with city 1 and city 2. So The King has to bomb any of these two cities and then invade the third city to conquer the country.