28292번 - 개미 수열

대구소프트웨어마이스터고등학교에 다니고 있는 changwook987은 베르나르 베르베르의 소설 『개미』를 읽다가 흥미로운 수열을 보았다.

$1$, $11$, $12$, $1121$, $\dots$

이 수열은 소설 『개미』에서 나와 개미 수열이라고 부르기도 하고 읽고 말하기 수열이라고 하기도 한다.

이 수열의 규칙은 이렇다.

1. 첫 번째 항은 $1$이다.
2. 이전 항의 이웃한 같은 숫자들을 묶는다.
   • 이전 항이 $11123333$일 경우 $(1, 1, 1), (2), (3, 3, 3, 3)$
3. 묶인 숫자들의 숫자와 개수를 붙여 쓴다.
   • 묶인 숫자들이 $(1, 1, 1), (2), (3, 3, 3, 3)$이므로 숫자와 개수를 붙여 쓰면 $132134$
4. 2, 3을 반복한다.

이 개미 수열을 관찰하다 보면 수가 빠르게 길어지지만, 수를 이루는 숫자가 커지기는 쉽지 않다는 것을 알 수 있다.

그렇다면 이 수열의 $N$번째 항의 자릿수 중에서 가장 큰 수는 무엇일까?

개미 수열의 $N$번째 항의 자릿수 중 가장 큰 수를 출력해 보자.

첫째 줄에 양의 정수 $N$이 주어진다. $(1 \le N \le 100)$

개미 수열의 $N$번째 항의 자릿수 중에서 가장 큰 수를 출력한다.

다음은 4번째 항까지의 개미 수열을 구하는 과정이다.

1. 첫 번째 항은 $1$이다.
2. 첫 번째 항이 $1$이므로 이웃한 같은 숫자들을 묶으면 $(1)$이 된다.
3. 묶은 숫자가 $1$ 한 개 뿐이므로 숫자와 개수를 붙여 쓰면 $11$이 된다.
4. 두 번째 항이 $11$이므로 이웃한 같은 숫자들을 묶으면 $(1, 1)$이 된다.
5. 묶은 숫자가 $1$ 두 개이므로 숫자와 개수를 붙여 쓰면 $12$가 된다.
6. 세 번째 항이 $12$이므로 이웃한 같은 숫자들을 묶으면 $(1), (2)$가 된다.
7. 묶은 숫자가 $1$ 한 개, $2$ 한 개이므로 숫자와 개수를 붙여 쓰면 $1121$이 된다.