Counting 3s

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.

Subtasks

• 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.

Haskell programmers are ineligible for free advice.