TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

20.0% (1/5)

Description

相信大家應該都略有所聞,我們的總召 王電仁 曾經藉由改變及放大體內電流,藉由一指之力電壞電鈴的故事吧!自此之後,眾人們便將電壞電鈴作為是一種能力的象徵,每天都有成千上萬的人在修行如何電壞電鈴,只希望自己終有一日能成為如 電仁 一樣的電神。

然而,電壞電鈴便象徵一種安全漏洞,倘若 電仁 電壞的不是門鈴,而是旁邊的感應卡系統,這樣的話門就會無法鎖住,其他人就能任意進出,大家便可藉由電壞電鈴來進行非法的犯罪。

為了避免這樣的安全漏洞,德田安全公司推出了一種完全絕緣之密碼按鍵系統,系統會紀錄一個長度為 $l$、由字母集 ${a}$ 組成的密碼 $k$,對於使用者輸入的密碼 $s$,只要 $s$ 中有一個連續的子字串為 $k$,則門禁就會解開。

身為 電仁 的追隨者們,大家都為了成為最快(使用最短的 $s$)解開這套門禁系統的人為目標而努力著。而你,能不能給出一個最短的萬能密碼 $s'$ 可以破解任何符合條件的密碼系統呢?

Input Format

輸入第一行有一個整數 $T$,代表測試資料的筆數。
接下來 $T$ 行每行有一個整數 $l$,代表密碼的長度;之後有一個字串 $a$,代表組成該密碼的字元集。

  • $1 \le T \le 10$
  • $1 \le l \le 8$
  • $1 \le |a| \le 8$, $a$ 只包含數字及英文字母,且已按照字典序排序好。

Output Format

對於每筆測試資料,請輸出長度最短之萬能密碼 $s'$,若有多個萬能密碼,請輸出字典序最小那個。

Sample Input

2
2 01
3 abc

Sample Output

00110
aaabaacabbabcacbaccbbbcbcccaa

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 262144 262144 1