시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 253 75 54 40.909%

문제

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

네온 사인은 총 N개의 꼭지점이 원의 둘레를 따라 찍혀져 있다. 그리고, 총 N * (N-1)개의 야광 튜브가 꼭지점을 연결하고 있다. 야광 튜브는 두 가지 색(빨간색과 파란색)이 있다.

시흠이는 한 번에 한 삼각형만 불을 밝히려고 한다. 이 때, 삼각형의 모든 변은 색상이 같아야 하고, 꼭지점이 서로 이어져 있어야 한다. 그는 이러한 단색 삼각형의 개수를 알려고 한다.

예를 들어, 아래 네온 사인에는 단색 삼각형이 두 개 있다. (1, 3, 5)와 (2, 3, 4)

네온 사인의 꼭지점의 수와 각 야광 튜브의 색상이 주어졌을 때, 단색 삼각형의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 꼭지점의 개수 N(3 ≤ N ≤ 1,000)이 주어진다. 다음 N-1개의 각 야광 튜브의 색이 주어진다. 이 줄의 i번째 줄에는 꼭지점 i와 연결된 튜브의 색상이 i+1번 꼭지점과 연결된 튜브부터 N번까지 순서대로 주어진다. 빨간색은 1, 파란색은 0으로 주어진다.

출력

각 테스트 케이스에 대해서 단색 삼각형의 개수를 출력한다.

예제 입력

2
5
1 1 0 1
0 0 0
0 1
1
5
1 1 1 1
0 0 1
0 1
1

예제 출력

2
4

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2011 H번