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

• Дошка більша: її довжина і ширина дорівнюють $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