https://codeforces.com/problemset/problem/2003/C

乌龟给了你一个由小写英文字母组成的字符串 \(s\)。

乌龟定义一对整数 \((i, j)\)（\(1 \le i < j \le n\)）为 愉快对（pleasant pair），当且仅当存在一个整数 \(k\) 满足 \(i \le k < j\)，并且同时满足以下两个条件：

\(s_k \ne s_{k+1}\)；

\(s_k \ne s_i\) 或 \(s_{k+1} \ne s_j\)。

此外，乌龟认为一对整数 \((i, j)\) 是一个 好对（good pair），当且仅当满足下列任意一个条件：

\(s_i = s_j\)，或者

\((i, j)\) 是一个愉快对。

现在，乌龟想要重新排列字符串 \(s\) 中的字符，使得其中的 好对数量尽可能多。

请你帮帮乌龟，输出一个重新排列后的字符串，使好对数最大化。

输入格式 每组测试数据包含多个测试用例。 第一行包含一个整数 \(t\)（\(1 \le t \le 10^4\)）——表示测试用例的数量。

每个测试用例包含两行：

第一行一个整数 \(n\)（\(2 \le n \le 2 \times 10^5\)）——字符串的长度；

第二行一个长度为 \(n\) 的字符串 \(s\)，由小写英文字母组成。

保证所有测试用例中 \(n\) 的总和不超过 \(2 \times 10^5\)。

输出格式 对于每个测试用例，输出一个字符串，是原字符串的重新排列，使得好对数量最大化。

如果存在多个方案，输出任意一个均可。

示例

输入

5
3
abc
5
edddf
6
turtle
8
pppppppp
10
codeforces

输出

acb
ddedf
urtlet
pppppppp
codeforces

说明

示例 1： 排列为 acb 后，只有一对好对 \((1, 3)\)。这是最多的好对数。其它如 bac、cab 也是合法解。

示例 2： 排列为 ddedf 后，好对有 \((1,2), (1,4), (1,5), (2,4), (2,5), (3,5)\) 等。

示例 4： 所有字符都相同，任意排列都能最大化好对数。