恭喜您被大师援助中心录取!然而,你在课堂上非常无聊,厌倦了无所事事,所以你给自己想出了一个游戏。
给定一个字符串 $$$s$$$ 和一个偶数 $$$n$$$。您可以对其应用两种类型的操作:
1. 将反转字符串 $$$s$$$ 添加到字符串 $$$s$$$ 的末尾(例如,如果 $$$s = $$$ cpm,则在应用操作 $$$s = $$$ cpmmpc 后)。
2. 反转当前字符串$$$s$$$(例如,如果$$$s = $$$ cpm,则在应用操作$$$s = $$$ mpc 后)。
需要确定在精确应用$$$n$$$操作后可以获得的按字典顺序最小的$$$^{\dagger}$$$字符串。请注意,您可以按任意顺序应用不同类型的操作,但总共必须应用精确的 $$$n$$$ 操作。
$$$^{\dagger}$$$当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个偶数 $$$n$$$ ($$$2 \leq n \leq 10^9$$$) — 应用于字符串 $$$s$$$ 的操作数。
每个测试用例的第二行包含一个字符串 $$$s$$$ ($$$1 \leq |s| \leq 100$$$),由小写英文字母组成,即应用操作的字符串。
输出
对于每个测试用例,输出一行 - 在精确应用 $$$n$$$ 操作后可以获得的按字典顺序排列的最小字符串。
示例
输入 #1
5 4 cpm 2 grib 10 kupitimilablodarbuz 1000000000 capybara 6 abacaba
输出 #1
cpm birggrib kupitimilablodarbuz arabypaccapybara abacaba
注意
在第一个测试用例中,您可以应用第二种类型的操作(即反转字符串 $$$s$$$)$$$4$$$ 次。那么字符串 $$$s$$$ 将保持等于 cpm。
在第二个测试用例中,您可以执行以下操作:
- 应用第二种类型的操作,之后 $$$s$$$ 将等于 birg。
- 应用第一种类型的操作(即,将反转的字符串 $$$s$$$ 添加到字符串 $$$s$$$ 的末尾),之后 $$$s$$$ 将等于 birggrib。