Arithmetic Right Shift

問題文

正整数 $K$ ち 0, 1 からなる文字列 $S$ が与えられます。
ここで、$S$ に対する以下の操作を算術右シフトといいます。

• $S$ の $1$ 文字目の文字を $S$ の先頭に挿入する。その後、$S$ の末尾の文字を $1$ つ削除する。

算術右シフトをちょうど $K$ 回行った後の $S$ を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1 \le T \le 10^4$
• $1 \le K \le 10^9$
• $T, K$ は整数である
• $S$ は 0, 1 からなる長さ $1$ 以上 $64$ 以下の文字列である

入力

入力は以下の形式で標準入力から与えられる。 ここで、$\mathrm{case}_i ~ (1 \le i \le T)$ は $i$ 個目のテストケースである。

各テストケースは以下の形式で与えられる。

出力

$T$ 行出力し、$i$ 行目には $i$ 個目のテストケースについての答えを出力せよ。

サンプル

4
2
0110
5
10101010
998244353
01
9
1101000000000111

0001
11111101
00
1111111111101000

$1$ 個目のテストケースについて、以下の手順で算術右シフトを $2$ 回行います。 ここで、$S_1$ を $S$ の $1$ 文字目の文字とします。

• $S =$ 0110 の先頭に $S_1 =$ 0 を挿入し、$S$ の末尾の文字を削除する。$S =$ 0011 に更新される。
• $S =$ 0011 の先頭に $S_1 =$ 0 を挿入し、$S$ の末尾の文字を削除する。$S =$ 0001 に更新される。

このようにして、0001 を得ることができます。

$2$ 個目のテストケースについて、$S_1=$ 1 を挿入し、$S$ の末尾の文字を削除する操作を $5$ 回行うと、11111101 を得ることができます。

$3$ 個目のテストケースについて、算術右シフトを行う回数が膨大になる場合に注意してください。