Pad strings with asterisks on either side to fill a given size of space. The string should appear in the centre, but if equal padding is not possible then the shorter padding should appear on the right of the string.

Input

The first line of the input contains the number of test cases. Each consecutive pair of lines provides an integer representing the size of space to fill and a string that needs to be padded.

Output

One string per line, which should be the asterisk-padded strings

Example

Input:
3
10
hello
10
milk
30
to be, or not to be

Output:
***hello**
***milk***
******to be, or not to be*****