問題文

正整数 $K$ と 0, 1 からなる文字列 $S$ が与えられます．

ここで，$S$ に対する以下の操作を算術右シフトといいます．

$S$ の $1$ 文字目の文字を $S$ の先頭に挿入する．その後，$S$ の末尾の文字を $1$ 文字削除する．

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

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

制約

• $T$ は整数である．
• $1 \le T \le 10^4$．

• $K$ は整数である．
• $1 \le K \le10^9$．

• $S$ は 0, 1 からなる文字列である．
• $1 \le |S| \le 64 \enspace (|S|$ は $S$ の長さである$)$．

入力

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

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

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

$K$
$S$

出力

$T$ 行出力し，$i ~ (1 \le i \le T)$ 行目には $i$ 個目のテストケースについての答えを出力せよ．

サンプル

4
2
0110
5
10101010
998244353
01
9
1101000000000111

0001
11111101
00
1111111111101000