Problem Description

Given a weighted undirected graph, how many edges must be on the minimum spanning tree of this graph?

Input

The first line of the input is a integer $T$, meaning that there are $T$ test cases.

Every test cases begin with a integer $n$ ,which is the number of vertexes of this graph.

Then $n-1$ lines follow, the $i^{th}$ line contain $n-i$ integers, the $j^{th}$ number $w$ in this line represents the weight between vertex $i$ and vertex $i+j$.

$1 \leq T \leq 20.$

$1 \leq n , w\leq 3,000.$

Output

For every test case output the number of edges must be on the minimum spanning tree of this graph.

2
3
1 1
1
4
2 2 3
2 2
3

0
1

Hint

For the second sample, $(2 , 4)$ is satisfied.