Традиционное гомоку, или пять в ряд, играется на небольшой доске и заканчивается сразу же, когда пять камней одного цвета выстраиваются в линию. Однако в «Новом гомоку» правила отличаются. Правила Нового гомоку следующие:

• Доска больше: её длина и ширина равны $1000$.
• Чёрный и белый игроки по очереди ставят свои камни, начиная с чёрного игрока. На координату, куда уже был поставлен камень, нельзя поставить камень снова.
• Если ровно $5$ камней одного цвета образуют непрерывную линию из пяти камней (по горизонтали, вертикали или диагонали под углом $45^\circ/135^\circ$ к горизонтальной линии), это называется пятёркой в ряд. Игра не заканчивается, когда одна из сторон собирает пятёрку в ряд.
• Игра заканчивается, когда достигнуто заранее заданное количество ходов.

Ваша задача — после каждого из $n$ ходов в заданной последовательности вывести общее количество пятёрок в ряд у игрока, который только что поставил свой камень.

Входные данные

В одном тестовом файле содержится несколько наборов входных данных. Первая строка входных данных содержит одно целое число $T$ ($1 \le T \le 10^4$), обозначающее количество наборов входных данных.

Для каждого набора входных данных:

• Первая строка содержит целое число $n$ ($1 \le n \le 10^4$), обозначающее количество ходов.
• Следующие $n$ строк содержат по два целых числа $x_i, y_i$ ($1 \le x_i, y_i \le 1000$), представляющих координаты $i$-го хода; гарантируется, что все координаты в рамках одного набора данных различны.

Гарантируется, что сумма $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