Training Site

# Counting 3s

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.0 seconds

Remi likes recording the number of times the $3$ digit occurs in integers. For example, the integer $3032$ has two $3$ digits.

While counting from $1$ up to some integer $N$ inclusive, Remi records the total number of $3$s encountered. Your task is to write a program that takes an integer $N$ as input and prints the total number of $3$s recorded by Remi for all integers together between $1$ to $N$ inclusive. The term inclusive means that Remi includes the integers $1$ and $N$ when counting.

## Input

There will be a single line containing the integer $N$.

## Output

You should print a single integer which is the total number of $3$s recorded by Remi while counting from $1$ to $N$ inclusive.

• Subtask 1 (+30%): $1 \le N \le 20$.
• Subtask 2 (+30%): $1 \le N \le 20\,000$.
• Subtask 3 (+20%): $1 \le N \le 2\,000\,000\,000$.
• Subtask 4 (+20%): $1 \le N \le 2\,000\,000\,000\,000\,000$.

## Sample Explanations

### Sample 1

In the sequence $1, 2, 3, 4$, where $N=4$, there is only one number that contains a digit $3$, which is $3$ itself. The total number of recorded $3$s is $1$.

### Sample 2

In the sequence $1, ..., 13$ there are two integers $3$ and $13$ that each contain one $3$, giving $2$ in total.

### Sample 3

In the sequence $1, ..., 72$ there are $16$ integers that contain $3$s. One of these integers contains two $3$s (this number is $33$), the rest have only a single $3$. The total is then $17$. Note that Sample 3 is not part of the first subtask.

## Note:

If you are using a type sensitive language such as C, C++, C#, or Java then be sure to use variables, functions, and methods that support 64-bit precision. The answer does not exceed the maximum value of a signed 64-bit integer in any test case.

• ### Sample Input 1

4


### Sample Output 1

1

• ### Sample Input 2

13


### Sample Output 2

2

• ### Sample Input 3

72


### Sample Output 3

17