어색한 모임

작은 마을에 사는 사람 $n$명이 공동체 $P$를 이룬다. $P$에 속한 두 사람은 서로 친할 수도 있고, 한 번도 만난 적이 없을 수도 있다. 서로 다른 두 사람 $x$와 $y$의 친밀도는 값 $f(x,y)$로 나타내며, $f(x,y) = f(y,x)$이다.

$P$의 부분집합 $F$를 모임이라고 부른다. $F$에 속한 사람 수를 $|F|$라고 하자. $|F|$가 $n$도 아니고 $1$도 아니며, $F$ 안의 서로 다른 두 사람 사이의 친밀도 중 최댓값이 $F$ 안의 사람과 $F$ 밖의 사람 사이의 친밀도 중 최솟값보다 항상 작으면 $F$를 어색한 모임이라고 한다. 즉 다음 두 조건을 모두 만족하는 $F$가 어색한 모임이다.

$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 \,\}$

서로 다른 두 사람의 친밀도가 모두 주어질 때, $P$의 어색한 모임이 몇 개인지 세는 프로그램을 작성하시오.

예를 들어 공동체 $P$에 $x$, $y$, $z$ 세 사람이 있다고 하자. $1 < |F| < 3$을 만족하는 모임은 $\{x,y\}$, $\{y,z\}$, $\{z,x\}$ 세 가지다. 친밀도가 $f(x,y) = 8$, $f(y,z) = 3$, $f(z,x) = 5$로 주어지면 이 가운데 어색한 모임은 $\{y,z\}$ 하나뿐이므로 답은 $1$이다.

입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 공동체 $P$의 사람 수 $n$이 주어진다 ($1 \le n \le 1000$). 사람은 $1$번부터 $n$번까지 번호로 구분한다. 이어지는 $n-1$개의 줄에는 친밀도가 주어진다. $i$번째 줄에는 $n-i$개의 정수 $h_{i,i+1}, h_{i,i+2}, \dots, h_{i,n}$이 공백 하나로 구분되어 주어진다. 여기서 $h_{i,j}$는 사람 $i$와 사람 $j$의 친밀도 $f(i,j)$이다 ($1 \le i < j \le n$, $1 \le h_{i,j} \le 10^6$).

출력은 표준 출력으로 한다. 각 테스트 케이스마다 정확히 한 줄을 출력한다. 그 줄에는 $P$의 어색한 모임의 개수를 출력한다.