디지털 시계

Timla는 자정에 집을 나섰고, 24시간 후인 다음 자정에 집으로 돌아왔다. 그 사이 집에 도둑이 들었다! 도둑은 00:00:00 이후에 침입했고, 24:00:00 이전에 집을 떠났음이 틀림없다.

Timla의 집에는 시간을 24시간 형식으로 시, 분, 초 단위로 표시하는 디지털 시계가 있다. Timla는 전기를 아끼는 것을 좋아해서, 집에 아무도 없을 때 시계는 자동으로 꺼진다. 정확히 얼마나 전기를 아꼈는지 측정하기 위해 그녀는 매우 정밀한 전력계도 가지고 있다. 이 전력계에 따르면, 그녀가 여행을 떠나 있던 하루 동안 시계는 $n$ 단위의 에너지를 소비했다. 시계의 각 숫자 세그먼트는 켜져 있는 매초마다 1단위의 에너지를 소비한다. 숫자는 그림과 같다.

그림 1: 디지털 시계의 숫자. 예를 들어 시계가 20:41:35를 표시할 때 27개의 숫자 세그먼트가 켜져 있다.

Timla는 경찰을 돕기 위해 도둑이 언제 집에 침입했을 수 있는지 알아내고 싶어 한다. 발자국을 보면 도둑은 집에 한 번 들어가고 한 번 나왔으므로, 시계가 여러 번 켜졌다 꺼졌을 수는 없다. 시계의 디스플레이는 항상 정확한 초 단위로 켜지고 꺼지며, 가장 이르면 00:00:00에 켜질 수 있고, 가장 늦으면 23:59:59를 표시한 후에 꺼질 수 있다.

양의 정수 $n$. 주어진 $n$에 대해, 하루 동안 시계가 $n$ 단위의 에너지를 소비하는 시간 구간이 적어도 하나 존재한다.

시계의 디스플레이가 켜졌을 수 있는 서로 다른 시각의 수를 출력한다.

• $n \le 3\,000\,000$

첫 번째 예시에서 시계는 정확히 1초 동안 켜져 있었음이 틀림없다. 11:11:17, 11:17:11 또는 17:11:11일 수 있다.

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

세 번째 예시에서 시계가 시작되었을 수 있는 경우는 3196가지이다. 예를 들어 20:02:06에 시작하여 20:02:08을 표시한 후에 꺼졌을 수 있다.