Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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 3s encountered. Your task is to write a program that takes an integer N as input and prints the total number of 3s 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 3s 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 3s 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 3s. One of these integers contains two 3s (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.

  • Sample Input 1

    4
    

    Sample Output 1

    1
    
  • Sample Input 2

    13
    

    Sample Output 2

    2
    
  • Sample Input 3

    72
    

    Sample Output 3

    17