三葉虫は地下鉄を建設するのが大好きです。彼は $n$ 本の路線を設計し、各路線には $n+1$ 個の駅の候補地があり、それらは平面上の座標で表されます。

地下鉄の体験を豊かにするため、三葉虫は各路線を線分にすることにしました！つまり、各路線について、三葉虫は2つの駅のみを選択し、その2つの駅の間に線分を引きます。乗客の乗り換えの煩雑さを最大化するため、三葉虫は建設する $n$ 本の地下鉄路線の間で、線分同士の交点の数を最小にすることを要求しています。なお、交点には始点と終点も含まれます。合法的な計画を立案してください。

要約：二次元平面上に $n$ 種類の色の点がそれぞれ $n+1$ 個ずつ与えられます。各色から異なる2つの点を選んで線分を引き、すべての $n$ 本の線分同士の交点の数が最小になるようにしてください。その構成を出力してください。

注意：2つの線分が共線である場合、交点の数は無限大と定義されます。すべての無限大は等しいものとみなします。

入力

入力は複数のテストケースから構成されます。最初の行にテストケースの数 $T$ が与えられます。各テストケースは以下の形式で与えられます。

1行目に路線の数 $n$ が与えられます。

続く $n$ 行には、各行に $2n+2$ 個の整数が与えられます。そのうち $2i-1$ 番目と $2i$ 番目の整数 $(x_i, y_i)$ は、現在の路線の駅の座標を表し、その駅の番号は $i$ です。

すべての駅の座標は互いに異なることが保証されています。

出力

各テストケースについて、$n$ 行を出力してください。各行には、その路線が接続する2つの駅の番号を空白区切りで出力してください。任意の解を出力すれば正解となります。

入出力例

入力 1

1
2
5 0 0 8 10 8
0 4 10 4 5 12

出力 1

1 3
1 3

注記

図中の青色と赤色の点はそれぞれ1号線と2号線の駅を表し、青い線と赤い線はそれぞれ1号線と2号線で選択された路線を表しています。

任意の解を出力すればよいため、以下のような出力も正解となります。

1 2
2 3

制約

すべてのデータについて：$1\le n\le1000,\sum n\leq 2000$、$|x_i|,|y_i|\le10^9$。