题目描述

正如题目所说，你有一个非常无聊的字符串，但是你厌倦了无所事事，于是你为自己想出了一个游戏。

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

1. 将字符串 $s$ 的反转字符串添加到 $s$ 的末尾（例如，如果 $s =$ cpm，操作后 $s =$ cpmmpc）。
2. 将当前字符串 $s$ 反转（例如，如果 $s =$ cpm，操作后 $s =$ mpc）。

要求你在恰好进行 $n$ 次操作后，得到字典序最小的字符串。注意，你可以以任意顺序选择不同类型的操作，但总共必须恰好进行 $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$ 次操作后可以得到的字典序最小的字符串。

输入输出样例

5
4
cpm
2
grib
10
kupitimilablodarbuz
1000000000
capybara
6
abacaba

cpm
birggrib
kupitimilablodarbuz
arabypaccapybara
abacaba

说明/提示

在第一个测试用例中，你可以对字符串 $s$ 进行 $4$ 次第二种操作（即反转字符串）。这样字符串 $s$ 会保持为 cpm。

在第二个测试用例中，你可以这样操作：

• 先进行一次第二种操作（反转字符串 $s$），此时 $s$ 变为 birg。
• 再进行一次第一种操作（将反转后的 $s$ 添加到末尾），此时 $s$ 变为 birggrib。