Cosmic Station

Two young programmers, Peter and Stancu, are hired by two cosmic agencies. Peter's agency builds a station made of modules. Some pairs of modules are joined by corridors so that you can travel between any two modules along exactly one path of corridors; in other words, the modules and corridors form a tree. No corridor joins a module to itself, and no two modules are joined by more than one corridor.

An outside module is connected to exactly one other module (shown white in the figure). The outside modules are labeled from 1 to $N$; they exist just for fun. An inner module is connected to more than one other module (shown black in the figure), and all of the station's equipment sits in the inner modules.

Peter's chiefs want to keep the number of inner modules secret. To hide it, Peter encodes the station by giving, for every pair of outside modules, the distance between them, i.e. the number of corridors on the unique path that joins them.

Stancu has promised his bosses to break Peter's code and recover the number of inner modules, but he is not experienced enough. Given the distances between every pair of outside modules, determine the number of inner modules.

The first line contains the number of test cases $T$. Each test case begins with a line containing the number of outside modules $N$ ($3 \le N \le 1024$). The next $N - 1$ lines give the pairwise distances between outside modules. The first of these lines lists, separated by single spaces, the distances from outside module 1 to outside modules $2, 3, \ldots, N$. The second line lists, also separated by single spaces, the distances from outside module 2 to outside modules $3, 4, \ldots, N$, and so on. The last line contains only the distance from outside module $N - 1$ to outside module $N$.

For each test case, print on its own line the number $M$ of inner modules of the station. In every test case $M$ is less than 1024.