Counting 3s
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 64bit precision. The answer does not exceed the maximum value of a signed 64bit 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