恭喜你被硕士助教中心录取！然而你在课上极度无聊，闲得发慌，于是给自己设计了一个小游戏。

给定一个字符串 $s$ 和一个偶数 $n$。你可以对它执行两种操作：

1. 将字符串 $s$ 的反转串追加到 $s$ 的末尾（例如：若 $s = \text{cpm}$，执行操作后 $s = \text{cpmmpc}$）。
2. 反转当前字符串 $s$（例如：若 $s = \text{cpm}$，执行操作后 $s = \text{mpc}$）。

要求你在恰好执行 $n$ 次操作后，得到字典序最小的字符串。注意：你可以按任意顺序、任意次数混合使用两种操作，但总操作次数必须恰好为 $n$ 次。

† 字典序定义

字符串 $a$ 的字典序小于字符串 $b$，当且仅当满足以下条件之一：

• $a$ 是 $b$ 的前缀，且 $a \neq b$；
• 在两个字符串第一个不同的位置上，$a$ 对应的字母在字母表中早于 $b$ 对应的字母。

输入

每个测试用例包含多组数据。第一行是一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。

每组测试用例的格式如下：

• 第一行：一个偶数 $n$（$2 \le n \le 10^9$），表示需要执行的操作总次数。
• 第二行：一个字符串 $s$（$1 \le |s| \le 100$），由小写英文字母组成，是初始字符串。

输出

对于每组测试用例，输出一行：执行恰好 $n$ 次操作后能得到的字典序最小的字符串。

样例

输入

5
4
cpm
2
grib
10
kupitimilablodarbuz
1000000000
capybara
6
abacaba

输出

cpm
birggrib
kupitimilablodarbuz
arabypaccapybara
abacaba

样例说明

• 第一组测试用例：可以连续执行 $4$ 次操作2（反转字符串），最终字符串仍为 $\text{cpm}$。
• 第二组测试用例：操作流程如下：
  1. 执行操作2，$s$ 变为 $\text{birg}$；
  2. 执行操作1，将 $\text{birg}$ 的反转串 $\text{grib}$ 追加到末尾，最终 $s = \text{birggrib}$。