تُلعب لعبة غوموكو (Gomoku) التقليدية، أو خمسة على التوالي، على لوحة صغيرة وتنتهي فورًا عندما تصطف خمس قطع من نفس اللون. ومع ذلك، في «غوموكو الجديدة» (New Gomoku)، تختلف القواعد. قواعد غوموكو الجديدة هي كما يلي:

• اللوحة أكبر حجمًا، حيث يبلغ طولها وعرضها $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