시계

Timla는 자정에 집을 나섰다가 24시간 뒤인 다음 날 자정에 돌아왔다. 그동안 집에 도둑이 들었다! Timla의 집에는 시, 분, 초를 항상 여섯 자리로 표시하는 24시간제 디지털 시계가 있다. Timla는 전기를 절약하는 것을 좋아해서, 집에 아무도 없으면 시계가 자동으로 꺼진다. 절약한 전력량을 정확히 측정하기 위해, 매우 정밀한 전력량계도 가지고 있다. 이 계량기에 따르면, Timla가 집을 비운 날 시계는 $N$에너지 단위를 소비했다. 시계의 각 숫자 선분은 켜져 있는 동안 매초 에너지 한 단위를 사용한다. 숫자는 그림과 같은 모양이다. 예를 들어, 시간이 02:41:35일 때 숫자 선분 27개가 켜진다.

Timla는 도둑이 집에 침입했을 가능성이 있는 시각을 알아내 경찰을 돕고 싶어 한다. 발자국을 보면 도둑은 집에 한 번 들어갔다가 한 번 나왔으므로, 시계가 여러 번 켜졌다 꺼질 수는 없다. 시계 화면은 항상 정확한 초의 경계에서 켜지고 꺼지며, 이르면 00:00:00에 켜졌을 수 있고 늦어도 23:59:59을 표시한 뒤에는 꺼졌을 수 있다.

화면이 켜졌을 수 있는 서로 다른 시각의 수를 계산하는 프로그램을 작성한다.

배점

여러 테스트 케이스 그룹으로 제출한 해답을 평가한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$20$| $N \leq 23$

$2$ |$20$| $N \leq 200$

$3$ |$20$| $N \leq 5000$

$4$ |$40$| 추가 제한 없음.

입력은 정수 $N$ ($1 \leq N \leq 3 \cdot 10^6$)로 이루어진다.

하루 중 시계가 정확히 $N$에너지 단위를 소비한 시간 구간이 적어도 하나 존재한다.

시계 화면이 켜졌을 수 있는 서로 다른 시각의 수를 정수로 출력한다.

첫 번째 예제에서 시계는 정확히 일 초 동안 켜져 있어야 한다. 11:11:17, 11:17:11, 또는 17:11:11 동안 켜져 있었을 수 있다.

두 번째 예제에서 유일한 가능성은 시계가 00:00:00부터 23:59:59까지 하루 종일 켜져 있었던 경우이다.

세 번째 예제에서 시계가 켜지기 시작했을 수 있는 시각은 3196개이다. 예를 들어, 20:02:06에 켜지기 시작하여 20:02:08을 표시한 뒤 꺼졌을 수 있다.