전통적인 오목(Gomoku)은 작은 바둑판에서 진행되며, 같은 색의 돌 다섯 개가 일렬로 놓이면 즉시 게임이 끝납니다. 하지만 "새로운 오목(New Gomoku)"에서는 규칙이 다릅니다. 새로운 오목의 규칙은 다음과 같습니다:

• 바둑판이 더 크며, 가로와 세로의 길이가 모두 $1000$입니다.
• 흑돌과 백돌 플레이어가 흑돌부터 시작하여 번갈아 가며 돌을 놓습니다. 이미 돌이 놓인 좌표에는 다시 돌을 놓을 수 없습니다.
• 같은 색의 돌 정확히 $5$개가 끊기지 않는 다섯 개의 직선(가로, 세로, 또는 수평선과 $45^\circ/135^\circ$를 이루는 대각선)을 이루도록 배열되면, 이를 하나의 오목(five in a row) 세트라고 부릅니다. 한쪽이 오목 세트를 완성하더라도 게임은 끝나지 않습니다.
• 미리 정해진 착수 횟수에 도달하면 게임이 끝납니다.

여러분의 과제는 주어진 $n$번의 착수 순서에서 각 착수가 이루어진 직후마다, 방금 돌을 놓은 플레이어가 가진 오목의 총개수를 출력하는 것입니다.

입력

하나의 테스트 파일에 여러 개의 테스트 케이스가 주어집니다. 입력의 첫째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 $T$ ($1 \le T \le 10^4$)가 주어집니다.

각 테스트 케이스에 대하여:

• 첫째 줄에는 착수 횟수를 나타내는 정수 $n$ ($1 \le n \le 10^4$)이 주어집니다.
• 다음 $n$개의 줄에는 각각 $i$번째 착수의 좌표를 나타내는 두 정수 $x_i, y_i$ ($1 \le x_i, y_i \le 1000$)가 주어지며, 같은 데이터 세트 내의 모든 좌표는 서로 다름이 보장됩니다.

모든 테스트 케이스에서 $n$의 총합은 $10^4$을 초과하지 않음, 즉 $\sum n \le 10^4$임이 보장됩니다.

출력

각 테스트 케이스마다 한 줄에 $n$개의 수를 출력합니다. 여기서 $i$번째 수는 $i$번째 착수 직후 방금 돌을 놓은 플레이어가 가진 오목의 총개수를 나타냅니다.

예제

예제 1

1
14
1 1
2 1
1 2
2 3
1 3
2 5
1 4
2 7
1 5
2 4
1 6
2 2
1 7
2 6

0 0 0 0 0 0 0 0 1 0 2 1 3 3