네온 사인

시흠이는 최근에 레스토랑 "삼각형"을 열고, 가게를 상징하는 네온 사인을 주문했다.

이 네온 사인은 원의 둘레를 따라 찍힌 $N$개의 꼭짓점으로 이루어진다. 서로 다른 두 꼭짓점을 잇는 야광 튜브가 모든 쌍마다 하나씩 놓여 있으므로, 튜브는 모두 $N \times (N - 1) / 2$개이다. 각 튜브는 빨간색 또는 파란색이다.

시흠이는 한 번에 삼각형 하나만 밝히려고 한다. 삼각형은 세 꼭짓점과 그 세 꼭짓점을 서로 잇는 세 튜브로 이루어지며, 세 튜브의 색이 모두 같을 때에만 밝힐 수 있다. 이렇게 세 변의 색이 모두 같은 삼각형을 단색 삼각형이라고 부른다.

꼭짓점의 개수와 모든 튜브의 색이 주어졌을 때, 단색 삼각형이 몇 개인지 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 꼭짓점의 개수 $N$ ($3 \le N \le 1000$)이 주어진다. 이어지는 $N - 1$개의 줄에 튜브의 색이 주어지는데, 그중 $i$번째 줄에는 꼭짓점 $i$와 꼭짓점 $i + 1, i + 2, \dots, N$을 잇는 튜브의 색이 이 순서대로 주어진다. 빨간색은 $1$, 파란색은 $0$으로 나타낸다.

각 테스트 케이스마다 단색 삼각형의 개수를 한 줄에 하나씩 출력한다.