369

Interview

Time limit1sMemory limit512 MB

Summary

Count the total claps in the 369 game from 1 to N, where each number contributes one clap per digit that is 3, 6, or 9.

Level: Easy2 of 10
Topics: Implementation, Math, Brute force, String
Solved: No attempts yet

Problem

Minsu is playing the 369 game with his classmates. In this game, several people sit in a circle, and the person at the starting position shouts 1. Going clockwise, each person's own number increases by 1: 2, 3, 4, and so on. When your own number comes around, if it does not contain 3, 6, or 9, you must say the number. If it does contain 3, 6, or 9, you must clap once for each such digit. Anyone who breaks the rule ends the game.

Minsu wonders how many claps he will hear in total if the game is played up to N while the rules are followed. For example, if N = 14, claps occur once each at 3, 6, 9, and 13, so he will hear 4 claps in total. If N = 36, claps occur at 3, 6, 9, 13, 16, 19, 23, 26, 29, 30, 31, 32, 33, 34, 35, and 36, and since 33 and 36 each require two claps, the total is 18. For a positive integer N, write a program that calculates and prints the total number of claps heard if the 369 game is played up to N while the rules are followed.

Input

The first line gives the integer N (1 ≤ N ≤ 10^6).

Output

Print the total number of claps as an integer.

Examples2

Example 1
Input
```
14
```
Expected output
```
4
```
Example 2
Input
```
36
```
Expected output
```
18
```