거듭제곱

바샤의 부모님이 생일 선물로 계산기를 주셨다. 바샤는 계산기의 기능을 빠르게 익혔고, 그중 거듭제곱 연산이 가장 마음에 들었다. 작은 수를 작은 지수로 거듭제곱해도 결과가 매우 커질 수 있다는 점에 그는 크게 놀랐다.

바샤는 아직 거듭제곱을 직접 계산하지 못하지만 배우고 싶어 한다. 먼저 정수 $a$와 $b$가 주어졌을 때 $a^b$의 십진수 표기가 몇 자리인지 구하려고 했으나 잘되지 않았다. 그래서 이학년 친구 로마에게 도움을 청했다. 로마는 무엇이든 거꾸로 하는 것을 좋아한다. 그는 바샤에게 정수 $k$가 주어졌을 때 $a^b$가 십진수 표기로 정확히 $k$자리가 되는 $a$와 $b$를 찾는 법부터 배우자고 제안했다. 그런 $a$와 $b$는 매우 많을 수 있으므로, 바샤는 이 조건을 만족하는 쌍 $(a, b)$의 개수를 세는 법을 배우려 했다.

바샤는 이것도 풀지 못했다. 이제 그는 여러분에게 도움을 청한다. 이 문제를 푸는 프로그램을 작성하라.

입력 파일에 양의 정수 $k$가 하나 주어진다 ($1 \le k \le 17$).

출력 파일에 서로 다른 쌍 $(a, b)$의 개수를 출력하라. 여기서 $a$와 $b$는 양의 정수이고, $a > 1$이며, $a^b$의 십진수 표기가 정확히 $k$자리이다.