Blue Gene, Jr.

IBM의 Blue Gene 프로젝트에서 영감을 받은 Universal Biological Machinery(UBM)의 대표가 UBM 최고의 소프트웨어 엔지니어인 당신을 불렀다. 회사가 비밀리에 후원하는 우주 개발 계획이 화성에서 바이러스 Areopagusvirus를 발견했다. 이 바이러스가 어떻게 변이하는지 계산하는 프로그램을 만들어야 한다.

입력은 비어 있지 않으며, 데이터 집합 최대 100개로 이루어진다. 각 데이터 집합은 아래 설명대로 주어지고, 데이터 집합 사이에 빈 줄은 없다.

데이터 집합 하나는 세 부분으로 이루어진다.

1. 시작 줄: START N 형태의 한 줄이다. $1 \le N \le 20$이다.
2. 바이러스 코드: 영숫자 $N$개로 이루어진 한 줄이다. 영숫자는 대문자 A부터 Z까지, 또는 숫자 0부터 9까지 중 하나다.
3. 끝 줄: END 한 줄이다.

마지막 데이터 집합 뒤에는 ENDOFINPUT 한 줄이 온다.

각 데이터 집합마다 출력 집합이 정확히 하나씩 있고, 출력 집합 사이에 빈 줄은 없다.

출력 집합 하나는 변이가 모두 끝나 안정된 바이러스 코드 한 줄이다. 바이러스 코드는 다음 규칙에 따라 변이한다.

1. 가장 먼저 변이하는 바이러스 구간은 코드의 첫 영숫자에서 시작해 코드의 가장 오른쪽 영숫자에서 끝난다.
2. 바이러스 구간의 첫 영숫자가 대문자면 그 영숫자는 불안정하다. 이 영숫자는 자신의 바로 오른쪽 바이러스 구간(5번 참고)에서 일어난 변이 횟수 $n$으로 변한다. $n$이 9보다 크면 $n$을 10으로 나눈 나머지로 변한다. 바로 오른쪽에 바이러스 구간이 없으면 0으로 변한다.
3. 바이러스 구간의 첫 영숫자가 1부터 9까지의 숫자 $n$이면 그 영숫자도 불안정하다. 이 영숫자는 $n-1$로 변한다. 그리고 자신에서 오른쪽으로 $n$칸 떨어진 영숫자에서 시작해 코드의 가장 오른쪽 영숫자에서 끝나는 바이러스 구간이 변이한다. 오른쪽으로 $n$칸 떨어진 자리에 영숫자가 없으면, 바로 오른쪽 바이러스 구간(5번 참고)이 있을 때 그 구간이 변이한다.
4. 바이러스 구간의 첫 영숫자가 0이면 그 영숫자는 안정되어 변이하지 않는다. 0은 그대로 남고, 변이가 일어났다고 세지 않는다.
5. 어떤 영숫자의 바로 오른쪽 바이러스 구간은 그 영숫자에서 오른쪽으로 한 칸 떨어진 영숫자에서 시작해 코드의 가장 오른쪽 영숫자에서 끝난다.