Cosmic Station#1399
The young programmers Peter and Stancu were hired by two cosmic agencies. Peter's agency constructed a station composed of modules. Some pairs of modules are linked by corridors in such a way that it is possible to go from each module to any other module by a unique path of corridors. There is neither a corridor that starts and ends in the same module nor two or more corridors that link the same two modules. Outside modules are each connected to exactly one other module and are labeled from to . They exist just for completeness. All the equipment of the station is concentrated in the inner modules—these are modules connected to more than one other module. The supervisors of Peter want to keep the number of inner modules secret. To hide this number, Peter encoded the topology of the station by providing, for each pair of outside modules, the distance between them (i.e., the number of corridors on the unique path between the modules).
Now Stancu faces a difficult task: he promised his bosses to decode Peter's encoding and determine the number of inner modules in the station. Unfortunately, he is not experienced enough. Help him. Write a program to solve this task.
The first line of the input file contains the number of test cases. Each test case starts with a line containing the number of outside modules (3 \leq N \leq 1024). Then N - 1 lines follow. On the first of these lines, the distances from outside module to the outside modules , , , are given, separated by single spaces. On the second line, also separated by single spaces, the distances from outside module to the outside modules , , , are given, and so on. The last line contains only the distance from outside module N-1 to outside module .
For each test case, the program must print on a separate line of the standard output the number of inner modules in the station. In all test cases, will be less than .
Example 1