뛰어오르는 콩

$N$개의 뛰어오르는 콩이 한 줄로 서 있습니다. 매 초마다 콩 하나가 뛰어오릅니다. 주어진 시간(초)이 지난 뒤 콩들이 어떤 순서로 서 있는지 구하세요.

설명을 위해 각 콩에 서로 다른 알파벳 대문자를 붙이고, 처음에는 콩들이 알파벳 순서, 즉 A, B, C, … 순으로 서 있다고 하겠습니다. 예를 들어 $N = 4$이면 처음 배열은 ABCD입니다.

• 1초에 콩 A가 뛰어올라 바로 오른쪽 콩(B)과 자리를 바꿉니다. 줄은 BACD가 됩니다.
• 2초에는 B의 차례입니다. 이번에는 두 번 자리를 바꾸는데, 먼저 A와, 다음으로 C와 바꿔 ACBD가 됩니다.

일반적으로 $s$초에는 지금까지 가장 적게 뛴 콩들 중 가장 왼쪽에 있는 콩이 뛰며, 그 콩은 연속해서 $s$번 자리를 바꿉니다. 한 번의 자리 바꾸기는 뛰는 콩을 바로 오른쪽 콩과 맞바꾸는 것입니다. 만약 뛰는 콩이 이미 맨 오른쪽에 있다면, 오른쪽으로의 자리 바꾸기는 회전하듯 감싸여서 그 콩이 맨 왼쪽으로 이동하고 나머지 콩은 모두 오른쪽으로 한 칸씩 밀립니다.

앞의 예를 ACBD에서 이어가면, 가장 적게 뛴 콩 중 가장 왼쪽은 C입니다. 지금은 3초이므로 C는 세 번 자리를 바꿉니다: ACBD → ABCD → ABDC → CABD. 4초에는 D의 차례입니다. 5초에는 네 콩이 모두 정확히 한 번씩 뛰었으므로, 이번에 뛰는 콩은 다시 맨 왼쪽에 서 있는 콩입니다.

프로그램은 하나 이상의 테스트 케이스로 채점됩니다. 각 테스트 케이스는 한 줄에 정수 $T$와 문자열 $S$로 주어집니다. 여기서 $0 < T < 10^9$은 초의 수이고, $S$는 콩들의 처음 배열입니다. $S$는 서로 다른 대문자('A'…'Z')로 이루어진, 비어 있지 않은 문자열입니다.

마지막 테스트 케이스 다음 줄에는 0 하나만 주어집니다.

각 테스트 케이스마다 다음 한 줄을 출력하세요.

k. S

여기서 $k$는 테스트 케이스 번호(1부터 시작)이고, $S$는 콩들이 $T$초 동안 뛴 뒤의 배열입니다.