Magic Contest

この問題は2ステップ問題です。

アリスとボブは有名なマジシャンである。2人は助手のキャサリンとともに、マジックコンテストで次のマジックを披露することにした。

• まず、ボブは部屋に入り、外部との連絡を断つ。ボブはキャサリンとのみ連絡できる。キャサリンはアリスに、長さ $N$ の二進文字列 $S$ を伝える。
• アリスは、長さが $N$ 以上 $2N+100$ 以下の二進文字列を作り、キャサリンに渡す。

1回目の実行の入力は、次の形式で与えられる。

0 $T$ $N_1$ $S_1$

1回目の実行では、各テストケースについてキャサリンに渡す二進文字列を1行に1つ、合計 $T$ 個出力する。

$i$ 番目のテストケースで出力する文字列の長さを $M_i$ とすると、$N_i\leq M_i\leq 2N_i+100$ を満たさなければならない。

• $1\leq T\leq 1\,000$.
• $1\leq N_i\leq 200\,000$ ().

ボブは、すべてのテストケースについて元の文字列 $S$ を正しく復元しなければならない。1つでも正しく復元できなかった場合、その提出の得点は $0$ 点となる。

すべての文字列を正しく復元した場合、得点はアリスが出力した文字列の長さによって決まる。$i$ 番目のテストケースについて、元の文字列の長さを $N_i$、アリスが出力した文字列の長さを ${}_{}$ とする。 を次のように定義する。