גומוקו (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