CF1935A Entertainment in MAC

恭喜你被录取到了 Master's Assistance Center！然而，你在课堂上感到非常无聊，厌倦了无所事事，于是你为自己想出了一个游戏。 给定一个字符串 $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$ 次操作后可以得到的字典序最小的字符串。

在第一个测试用例中，你可以对字符串 $s$ 进行 $4$ 次第二种操作（即反转字符串）。这样字符串 $s$ 会保持为 cpm。 在第二个测试用例中，你可以这样操作： - 先进行一次第二种操作（反转字符串 $s$），此时 $s$ 变为 birg。 - 再进行一次第一种操作（将反转后的 $s$ 添加到末尾），此时 $s$ 变为 birggrib。 由 ChatGPT 4.1 翻译