#P18020. Optimal Splitting

Optimal Splitting

Optimal Splitting

给定一个长度为 NN、仅含小写英文字母的字符串 SS。把 SS 的每个字符恰好分配给两个子序列 X,YX,Y 中的一个,子序列中的字符保持它们在 SS 中的先后顺序。允许某个子序列为空。

若 ∣X∣<∣Y∣|X|<|Y|,交换两者,使得 ∣X∣≥∣Y∣|X|\ge|Y|。在 YY 末尾补上若干个字符 a,直到 ∣Y∣=∣X∣|Y|=|X|。然后构造长度为 ∣X∣|X| 的字符串 ZZ,其中

Zi=max⁡(Xi,Yi),Z_i=\max(X_i,Y_i),

字符大小按照英文字母顺序比较。求所有分配方式中,字典序最小的 ZZ。

字典序规定:如果一个字符串是另一个字符串的真前缀,则较短者更小;否则比较第一个不同位置上的字符。

输入格式

第一行一个整数 TT。每组数据第一行一个整数 NN,第二行一个长度为 NN 的字符串 SS。

输出格式

每组数据输出一行,表示字典序最小的字符串 ZZ。

数据范围

1≤T≤1041\le T\le10^4,1≤N≤50001\le N\le5000。SS 只含小写英文字母。所有测试用例的 N2N^2 之和不超过 500025000^2。

样例 1

输入

3
1
a
2
za
5
ababa

输出

a
z
aba