RATS 수열

RATS(reverse add then sort) 함수는 십진 정수 하나를 받아서, 자릿수가 작은 것부터 큰 순서로 놓인 십진 정수를 돌려준다.

값은 다음 세 단계로 구한다.

1. 입력 값의 자릿수를 뒤집는다.
2. 뒤집은 값을 원래 값에 더한다.
3. 합의 자릿수를 오름차순으로 정렬하고, 앞에 오는 0은 버린다.

RATS(12334444): 12334444 + 44443321 = 56777765 -> 55667777
RATS(44556): 44556 + 65544 = 110100 -> 111

이 문제에서 다루는 수열은 첫 항이 임의로 주어지고, 그다음 항부터는 바로 앞 항의 RATS 값이다. 예를 두 개 들면 다음과 같다.

12334444, 55667777, 123334444, 556667777, 1233334444, 5566667777, ...
123, 444, 888, 1677, 3489, 12333, 44556, 111, 222, 444, 888, ...

첫 번째 수열을 크리퍼(creeper)라고 부른다. 이 규칙적인 모양을 유지하면서 무한히 커진다는 사실이 증명되어 있다. 어떤 항이 크리퍼에 속하려면 12 뒤에 숫자 3이 $a$개 오고 그 뒤에 4444가 오는 모양이거나, 55 뒤에 숫자 6이 $a$개 오고 그 뒤에 7777이 오는 모양이어야 하며, 이때 $a \ge 2$다. 두 번째 수열은 순환에 빠지고, 열 번째 항에서 앞선 값이 처음으로 다시 나온다. 모든 RATS 수열은 언젠가 크리퍼에 들어가 무한히 커지거나 두 번째 수열처럼 순환한다고 추측되고 있다.

시작 값이 주어지면 RATS 수열의 첫 $M$개 항을 구하는 프로그램을 작성하라. 첫 $M$개 항 안에서 같은 값이 다시 나오는지, 또는 크리퍼에 들어가는지도 판정해야 한다.

첫 줄에 데이터 집합의 개수 $P$가 주어진다($1 \le P \le 10000$). 각 데이터 집합은 서로 독립이고 같은 방법으로 처리한다.

이어지는 $P$개 줄에 데이터 집합이 한 줄에 하나씩 주어진다. 각 줄에는 데이터 집합 번호 $K$, 공백 하나, 구할 항의 개수 $M$($1 \le M \le 60$), 공백 하나, RATS 수열의 시작 값이 차례로 온다. 시작 값도 한 항으로 센다. 시작 값은 왼쪽부터 자릿수가 줄어들지 않는 순서로 놓인 십진 정수이고, 자릿수는 최대 40개다. 뒤따르는 항은 이보다 길어질 수 있다.

데이터 집합마다 한 줄을 출력한다. 첫 항의 번호를 1로 두고 $M$번째 항까지 차례로 살핀다.

첫 $M$개 항 안에 크리퍼에 속하는 항이 있으면 데이터 집합 번호, 공백, 대문자 C, 공백, 크리퍼에 처음 들어간 항의 번호를 출력한다.

그렇지 않고 첫 $M$개 항 안에 같은 수열의 앞선 항과 값이 같은 항이 있으면 데이터 집합 번호, 공백, 대문자 R, 공백, 값이 처음으로 반복된 항의 번호를 출력한다.

둘 다 아니면 데이터 집합 번호, 공백, $M$번째 항을 출력한다.