개미 수열

대구소프트웨어마이스터고등학교에 다니는 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$이 주어진다. ($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$이 된다.