B. Prefix and Suffix Can Be the Same
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In this problem, a prefix of a string means a consecutive substring starting from its first character. For example, the prefixes of the string icpc are i, ic, icp, and icpc. Similarly, a suffix of a string means a consecutive substring ending at its last character. For example, the suffixes of the string icpc are icpc, cpc, pc, and c.

Given a string $$$s$$$, find the shortest string other than $$$s$$$ itself having $$$s$$$ as both its prefix and its suffix. It can be proven that such a string is unique.

Input

The input consists of at most $$$50$$$ test cases, each in the following format.

$$$n$$$
$$$s$$$

The first line contains an integer $$$n$$$ between $$$1$$$ and $$$50,$$$ inclusive. The second line contains a string $$$s$$$ of length $$$n,$$$ consisting of English lowercase letters.

The end of the input is indicated by a line consisting only of a zero.

Output

For each test case, output in a line the shortest string other than $$$s$$$ having $$$s$$$ as both its prefix and its suffix.

Example
Input
4
test
4
icpc
8
cccpppcc
1
i
9
strongest
3
ttt
0
Output
testest
icpcicpc
cccpppcccpppcc
ii
strongestrongest
tttt