Fairies and Witches

Pari is a powerful fairy who fights to protect Fairyland from evil witches. The witches grow stronger every day, so Pari must arrange magical sticks into a convex polygon with non-zero area to cast a protection spell. Pari cannot use whichever sticks she wants, though. The sticks in Fairyland form a graph in which the edges are sticks and the nodes are endpoints of one or more sticks. The sticks touch each other only at endpoints, since they are magical. When Pari removes a stick to use in her spell, every stick that shared a node with it disappears forever and can no longer be used. Pari wonders how many distinct subsets of sticks can be removed and used to form a convex polygon with non-zero area. All sticks are distinct, even those with the same length. Two subsets are distinct if at least one stick is in one but not the other. A subset is valid only if there is a way to remove all of its sticks from the graph without any of them disappearing.

The first line contains the number of test cases $T$. Each test case begins with a line containing the integer $N$, the number of nodes in the graph. Then $N$ lines follow, each containing $N$ integers. The $j$-th value on the $i$-th line is $L_{i,j}$, the length of the stick with endpoints at nodes $i$ and $j$, or 0 if there is no such stick.

For each test case, output one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of valid subsets described above.

$1 \le T \le 100$. $0 \le L_{i,j} \le 1000$ for all $i, j$. $L_{i,i} = 0$ for all $i$. $L_{i,j} = L_{j,i}$ for all $i, j$.