첫 번째 항

다음과 같이 이어지는 수열이 있다.

1, 11, 21, 1211, 111221, ...

어떤 항에서 다음 항을 만드는 방법은 이렇다. 현재 항을 같은 숫자가 이어지는 구간으로 쪼갠 다음, 구간마다 그 숫자가 반복된 횟수를 앞에, 숫자 자체를 뒤에 적어 차례대로 이어 붙인다. 예를 들어 21은 2가 한 개, 1이 한 개이므로 다음 항은 1211이다. 같은 규칙으로 111221은 1이 세 개, 2가 두 개, 1이 한 개이므로 그 다음 항은 312211이다.

규칙을 거꾸로 적용하면 이전 항도 알아낼 수 있다. 2221은 2가 두 개, 1이 두 개라는 뜻이므로 이전 항은 2211이고, 2211의 이전 항은 221이다. 그런데 221에는 이전 항이 없다. 자릿수가 홀수여서 (횟수, 숫자) 쌍으로 나눌 수 없기 때문이다. 2212에도 이전 항이 없다. 쌍으로 읽으면 2가 두 개, 2가 한 개인 222가 나오지만, 222의 다음 항은 2212가 아니라 32이기 때문이다.

항 n이 주어지면 이 규칙을 따르는 수열 중 n이 등장하는 수열의 첫 번째 항을 구하는 프로그램을 작성하시오. 첫 번째 항은 이전 항이 존재하지 않는 항이다. n이 2221이면 답은 221이고, n이 312211이면 답은 1이다. 22처럼 이전 항이 자기 자신과 같은 경우에는 예외로 그 항을 첫 번째 항으로 본다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 줄에 최대 100자리인 정수 n이 하나씩 주어진다. 마지막 줄에는 0이 주어지며, 이 줄은 처리하지 않는다.

테스트 케이스마다 한 줄씩 Test i: a 형식으로 출력한다. i는 1부터 시작하는 테스트 케이스 번호이고, a는 첫 번째 항이다.