程序设计能力实训

1253. 构造字典序最小字符串

单点时限: 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
不限期开放

题目列表