豊かな国 AA は、$1$ から $n$ まで番号が付いた $n$ 個の都市と $n-1$ 本の道路からなります。道路の設計が優れているため、どの都市から出発しても、いくつかの道路を通って目的の都市に到達できます。

AA の王 Dreamoon は明日すべての都市の治安を視察したいので、経路を計画しました。その経路は、都市 $1$（AA の首都）から出発して都市 $1$ に戻る、$2\times n-2$ 本の辺を通る経路です。記録しやすいように、Dreamoon はこの経路上の都市の番号を順番に紙に書きました。

しかし、残念ながら Dreamoon は紙にミルクティーをこぼしてしまい、連続するいくつかの番号が読めなくなりました。良い旅をするために、この読めない番号の復元をあなたに頼みました。

解が複数ある場合、辞書順で最小の解を出力してください。また、与えられる入力には少なくとも一つの解が存在することが保証されます。

入力

最初の行にはテストケース数を表す整数 $T$ が一つ含まれます。以下に入力データセットを説明します。

各テストケースは二行からなります。最初の行には、AA の都市数を表す整数 $n$ が一つ含まれます。二行目には、$0$ 以上 $n$ 以下の整数が $2\times n-1$ 個含まれ、$i$ 番目の数はこの経路の $i$ 番目の都市を表します。$i$ 番目の数が $0$ なら、こぼれたミルクティーによってその番号が読めないことを意味します。すべての $0$ は連続しており、少なくとも一つの $0$ が存在することが保証されます。

制約

• $1\le T\le30\,000$.

• $1\le n\le300\,000$.

• 都市には $1$ から $n$ まで番号が付いています。

• Dreamoon が紙に書いた都市番号のうち少なくとも一つが読めず、読めない番号はすべて連続しています。

• 全テストケースにわたる $n$ の合計は $300\,000$ 以下です。

出力

各テストケースについて、復元した経路を表す、$1$ 以上 $n$ 以下の数 $2\times n-1$ 個を一行に出力してください。解が複数ある場合は辞書順で最小の解を出力してください。与えられる入力には少なくとも一つの解が存在することが保証されます。

入出力例

入力 1

9
5
1 2 3 2 0 2 1 5 1
5
1 2 3 0 0 2 1 5 1
5
1 2 0 0 0 2 1 5 1
5
1 2 0 0 0 0 1 5 1
5
1 0 0 0 0 0 1 5 1
5
1 0 0 0 0 0 0 5 1
5
1 0 0 0 0 0 0 0 1
5
1 0 0 0 0 0 0 0 0
5
0 0 0 0 0 0 0 0 0

出力 1

1 2 3 2 4 2 1 5 1
1 2 3 2 4 2 1 5 1
1 2 3 2 4 2 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1
1 2 1 3 1 4 1 5 1