伝統的な五目並べ（Gomoku）は小さな盤面で行われ、同じ色の石が 5 つ一列に並んだ時点で直ちにゲームが終了します。しかし、「新五目並べ（New Gomoku）」ではルールが異なります。新五目並べのルールは以下の通りです：

• 盤面はより大きく、縦と横の長さはともに $1000$ である。
• 黒番と白番のプレイヤーが、黒番から始めて交互に石を置く。すでに石が置かれている座標には再び石を置くことはできない。
• 同じ色の石がちょうど $5$ 個、途切れることなく一直線に並んだ場合（水平、垂直、または水平線に対して $45^\circ/135^\circ$ の斜め方向）、それを 1 組の五連と呼ぶ。一方が五連を作ってもゲームは終了しない。
• あらかじめ定められた手数に達した時点でゲームが終了する。

あなたの仕事は、与えられた $n$ 手の着手列において、各手が打たれた直後に、その手を打ったプレイヤーが持つ五連の総数を出力することです。

入力

1 つのテストファイルに複数のテストケースが含まれます。入力の最初の行には、テストケースの個数を表す整数 $T$ ($1 \le T \le 10^4$) が与えられます。

各テストケースについて：

• 最初の行には、手数を表す整数 $n$ ($1 \le n \le 10^4$) が与えられます。
• 続く $n$ 行には、それぞれ $i$ 手目の座標を表す 2 つの整数 $x_i, y_i$ ($1 \le x_i, y_i \le 1000$) が与えられます。同じデータセット内のすべての座標は互いに異なることが保証されます。

すべてのテストケースにおける $n$ の総和は $10^4$ を超えないこと、すなわち $\sum n \le 10^4$ が保証されます。

出力

各テストケースについて、$n$ 個の数値を 1 行に出力してください。$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