Lexicographically Smallest Rotation

You are given a string S of length N. Your task is to compute the lexicographically smallest string that can be obtained by any number of right circular rotations of S.

A right circular rotation means taking the last character of the string and placing it at the beginning. For example, if S = "abcd", the rotations are:

• Rotation 0 (original): abcd
• Rotation 1: dabc
• Rotation 2: cdab
• Rotation 3: bcda

The answer is the smallest string in lexicographic order among all rotations.

Formally, if we denote a right circular rotation by R_i(S) (rotating i times), then you need to find:

[ \min_{0 \le i < N} R_i(S) ]

Read from standard input and write the result to standard output.

inputFormat

The input is read from stdin and has the following format:

T
N1 S1
N2 S2
... 
NT ST

Where:

• T is the number of test cases.
• For each test case, an integer N (the length of the string) is given followed by the string S (length N).

outputFormat

For each test case, output on a separate line the lexicographically smallest string obtained by any number of right circular rotations of S. The output is written to stdout.

## sample

2
4 abcd
3 cba

abcd
acb

</p>