Awkward Group

A community $P$ is made up of $n$ people who live in a small town. Two people in $P$ may be friends, or they may never have met. The closeness of two distinct people $x$ and $y$ is a value $f(x,y)$, and $f(x,y) = f(y,x)$.

Call a subset $F$ of $P$ a group, and write $|F|$ for the number of people in it. $F$ is an awkward group if $|F|$ is neither $n$ nor $1$ and the largest closeness between two distinct members of $F$ is strictly smaller than every closeness between a member of $F$ and someone outside $F$. That is, $F$ is awkward when it satisfies both conditions:

$1 < |F| < n$

$\max\{\, f(x,y) \mid x \ne y,\ x \in F,\ y \in F \,\} < \min\{\, f(x',y') \mid x' \in F,\ y' \in P - F \,\}$

Given the closeness of every pair of distinct people, write a program that counts the awkward groups of $P$.

For example, suppose $P$ holds three people $x$, $y$ and $z$. The groups with $1 < |F| < 3$ are $\{x,y\}$, $\{y,z\}$ and $\{z,x\}$. If the closeness values are $f(x,y) = 8$, $f(y,z) = 3$ and $f(z,x) = 5$, the only awkward group among them is $\{y,z\}$, so the answer is $1$.

Read from standard input. The first line holds the number of test cases $T$. The first line of each test case holds $n$, the number of people in the community $P$ ($1 \le n \le 1000$). The people are numbered $1$ to $n$. The next $n-1$ lines hold the closeness values. Line $i$ holds $n-i$ integers $h_{i,i+1}, h_{i,i+2}, \dots, h_{i,n}$ separated by single spaces, where $h_{i,j}$ is $f(i,j)$, the closeness of person $i$ and person $j$ ($1 \le i < j \le n$, $1 \le h_{i,j} \le 10^6$).

Write to standard output. Print exactly one line for each test case. The line holds the number of awkward groups of $P$.