시에르핀스키 둘레

폴란드 수학자 바츠와프 시에르핀스키(1882-1969)는 1915년 집합론 연구의 일환으로 시에르핀스키 삼각형이라는 2차원 도형을 발표했다. 이 삼각형은 실제로 무한한 점의 집합이며, 다음 알고리즘으로 만들 수 있다.

1. 처음 도형은 꽉 찬 삼각형이다.
2. 현재 도형을 가로와 세로 모두 절반으로 줄이고, 같은 도형을 두 개 더 만든다(총 세 개).
3. 세 도형을 서로 이웃한 것끼리 꼭짓점에서 닿도록 배치한다. 현재 도형을 이 세 도형의 합집합으로 둔다.
4. 2번부터 반복한다.

다음은 처음 몇 번의 반복을 나타낸 그림이다.

iteration	0	1	2	3	4

반복을 무한히 계속하면 이 과정은 무한히 많은 연결된 점을 만든다. 하지만 반복 횟수가 유한한 경우를 생각해 보자. 처음 삼각형의 둘레가 3일 때, 주어진 반복에서 모든 (검은) 삼각형의 둘레의 합은 얼마인가? 정확한 둘레가 아니라, 그 정수 부분을 나타내는 데 필요한 십진 자릿수를 구하는 프로그램을 작성하라. 즉, 둘레보다 크지 않은 가장 큰 정수를 십진법으로 나타내는 데 필요한 자릿수를 구하라.

각 테스트 케이스는 반복 횟수를 나타내는 음이 아닌 정수 0 ≤ n ≤ 10,000 하나로 이루어진 줄이다.

각 케이스마다 케이스 번호에 이어, 주어진 반복 횟수에서 둘레의 정수 부분을 나타내는 데 필요한 십진 자릿수를 출력한다. 출력 형식은 아래 샘플 출력을 따른다.