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ドル$이 된다.