Given a string s with distinct lowercase English characters, find all the permutations of s.

Example:

s: “abc”
Permutations:
“abc”
“acb”
“bac”
“bca”
“cab”
“cba”

Testing

Input Format 

The first line contains an integer ‘T’, denoting the number of test cases.

For each test case, the input has two lines:

• An integer ‘n’ denoting the length of the string s.
• The string ‘s’.

Output Format

For each test case, the output has n! lines. Each line has one of the permutations of s.

Sample Input

2
4
abcd
1
a

Expected Output

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
a

Constraint

1 <= T <= 100
1 <= n <= 8