1225 人解决，1380 人已尝试。
1700 份提交通过，共有 4516 份提交。
0.9 EMB 奖励。
3038. 构造字典序最小字符串
单点时限: 2.0 sec
内存限制: 256 MB
给定长度为 N 的字符串 S，要构造一个长度为 N 的字符串 T。起初，T 是一个空串，随后反复执行下列两个操作中的任意一个，最终 目标是构造字典序尽可能小的字符串 T。
操作一：从 $S$ 的头部取一个字符，加到 $T$ 的尾部。
操作二：从 $S$ 的尾部取一个字符，加到 $T$ 的尾部。
例如：输入 $N=6$，S=ACDBCB；构造的 T=ABCBCD
具体按下图进行操作。
输入格式
第 1 行：整数 $T(1≤T≤10)$ 为问题数。
第 2 行：第一个 问题中的 $N(1≤N≤500)$，表示字符串 $S$ 的长度。
第 3 行：输入一个字符串 $S$，只包含大小写英文字母。
第 4 ~ 2*T+1 行：后面问题的数据 ，格式与第 1 个问题相同。
输出格式
对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等），然后 输出由 S 字符串构造出来的 字典序尽可能小的字符串 T。
样例
Input
3 2 ba 5 SORTS 10 Sarumanarm
Output
case #0: ab case #1: SORST case #2: Samranamru