Prof. Pang은 중국식 체커(Chinese Checkers)를 하고 있습니다. 게임 보드는 위 그림과 같습니다. 보드 위에는 $n$개의 체커가 있습니다. Prof. Pang은 현재 보드에서 가능한 서로 다른 이동이 몇 가지인지 알고 싶어 합니다.

한 번의 이동은 여러 단계로 구성됩니다. 처음에 Prof. Pang은 이동할 체커 $a$를 하나 선택해야 합니다. 각 단계에서 Prof. Pang은 다른 체커 $b$를 피벗으로 선택하고, 체커 $a$를 체커 $b$에 대해 대칭인 위치로 이동시킵니다. (한 번의 이동 중에 Prof. Pang은 단계 사이에서 $a$에 대한 선택을 바꿀 수 없습니다. 만약 한 단계를 거친 후 체커 $a$가 이동 전의 위치로 돌아온다면, 이 단계는 허용되지 않습니다.) 피벗 $b$에 대해서는 다음과 같은 몇 가지 조건이 있습니다.

• $a$와 $b$를 잇는 선분은 좌표축 중 하나와 평행해야 합니다. 참고: 육각형 보드에는 세 개의 축이 있습니다. 그중 하나는 수평이며, 임의의 두 축은 $\pi/3$의 각도로 교차합니다.
• $a$와 $b$가 인접할 필요는 없습니다.
• $a$와 그 대칭 위치를 잇는 선분 위에는 $b$ 외에 다른 체커가 있어서는 안 됩니다.
• 대칭 위치는 육각형 보드 내에 있어야 하며, 다른 체커가 점유하고 있지 않아야 합니다.

이동은 최소 한 단계 이상이어야 합니다. 첫 번째 단계 이후, Prof. Pang은 원할 때 언제든지 멈출 수 있습니다. 또한 Prof. Pang은 보드 위의 어떤 체커든 이동할 체커로 선택할 수 있습니다. Prof. Pang이 만들 수 있는 서로 다른 이동의 수를 출력하십시오. 두 이동은 두 이동 후에 모든 체커의 위치 집합이 다를 때만 서로 다른 것으로 간주합니다. 즉, 체커들은 서로 구별할 수 없습니다.

그림 1. 중국식 체커 보드

입력

첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어집니다. 각 테스트 케이스의 첫 번째 줄에는 체커의 수 $n$ ($1 \le n \le 121$)이 주어집니다. 이어지는 $n$개의 줄에는 체커의 위치를 나타내는 두 개의 정수가 주어집니다. 첫 번째 숫자는 몇 번째 행인지, 두 번째 숫자는 해당 행에서 몇 번째 위치인지를 나타냅니다. 행은 위에서 아래로, 위치는 왼쪽에서 오른쪽으로 1부터 시작하여 셉니다. 체커들의 위치는 서로 다름이 보장됩니다.

출력

각 테스트 케이스마다 한 줄에 하나씩 서로 다른 이동의 수를 출력하십시오.

예제

입력 1

5
1
1 1
2
1 1
2 1
2
9 4
9 6
10
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
10
1 1
2 1
2 2
5 7
3 2
3 3
4 1
4 2
4 3
4 4

출력 1

0
1
2
6
13