Neon Sign

Siheum recently opened a restaurant called "Triangle" and ordered a neon sign to represent it.

The neon sign has $N$ vertices placed along the circumference of a circle. A glowing tube connects every pair of distinct vertices, so there are $N \times (N - 1) / 2$ tubes in total. Each tube is either red or blue.

Siheum wants to light up exactly one triangle at a time. A triangle consists of three vertices and the three tubes joining them, and it can be lit only when all three tubes share the same color. Such a triangle, whose three sides are all the same color, is called a monochromatic triangle.

Given the number of vertices and the color of every tube, write a program that counts the monochromatic triangles.

The first line contains the number of test cases $T$.

The first line of each test case contains the number of vertices $N$ ($3 \le N \le 1000$). The next $N - 1$ lines describe the tube colors: the $i$-th of these lines lists the colors of the tubes joining vertex $i$ to vertices $i + 1, i + 2, \dots, N$, in that order. Red is written as $1$ and blue as $0$.

For each test case, print the number of monochromatic triangles on its own line.