N jumping beans are standing in a line. At each second, a bean jumps. Your assignment is to figure the final position of the beans after a given number of seconds. To make the explanation easier, let’s assign a unique letter to each bean, and for simplicity, let’s assume the beans are initially standing in order: A, B, C, etc. To simplify even further, let’s assume N = 4, so initially the beans are standing in the order ABCD. At the first second, A jumps, swapping its place with B. Now the order is BACD. At the second second, it’s B’s turn, but this time swapping its place with A, then C, resulting in the standing order ACBD. More formally: at second s, the left most bean that has jumped the least number of times will do the swap s times, each time swapping its place with the bean on its right. Note that when the right-most bean swaps, it moves to the left-most position, pushing everybody else one place to the right. So, continuing with the previous example, and starting with the arrangement ACBD, it is bean C’s turn, since it is the left-most bean that has jumped the least amount of times. Being at the third second, C will swap three times, first resulting in ABCD, then ABDC, and then CABD. At the fourth second, it’s bean D’s turn to jump. At the fifth second, and since all the four beans have jumped exactly once, the bean that will jump is the bean standing at the left-most position.

Input

Your program will be tested on one or more test cases. Each test case is specified on a single line specifying an integer T and a string S where (0 < T < 10⁹ ) is the number of seconds and S is the initial arrangement of the beans. S is a non empty string made of different upper-case letters (’A’. . . ’Z’).
The last test case is followed by a line having a single 0.

Output

For each test case, print the following line:
k. S
Where k is the test case number (starting at one,) and S is the arrangement of the beans after jumping for T seconds.

Example

Input:
3 ABCD
13 ACM
0

Output:
1. CABD
2. CAM