Chain Rounding Discrepancy

Bessie is used to the standard rounding procedure: to round a positive integer \(a\) to the nearest power of 10, say \(10^b\) with \(b\) a positive integer, she does the following:

• Let \(x\) be the \(b^{th}\) digit from the right (so for a \(P\)-digit number, \(b=P\)).
• If \(x\ge5\) then she adds \(10^b\) to \(a\).
• She then replaces the last \(b\) digits with zeros.

For example, if Bessie wishes to round \(456\) to the nearest hundred (i.e. \(10^2\)), she first finds that the second digit from the right is \(5\) (so \(x=5\)). Since \(5\ge5\) she adds \(10^2=100\) to \(456\) and then zeroes out the last two digits, yielding \(500\). (Similarly, \(446\) would be rounded to \(400\).)

Elsie, however, has invented a new method called chain rounding. In this method, to round to the nearest \(10^b\) one first rounds to the nearest \(10^1\), then rounds that result to the nearest \(10^2\), and so on up to \(10^b\).

For a given positive integer \(x\) we define \(P\) to be the smallest positive integer for which \(10^P\ge x\). Let \(f(x)\) be the result of Bessie’s one‐step rounding to \(10^P\) and let \(g(x)\) be the result of Elsie’s chain rounding process (i.e. first round \(x\) to the nearest \(10^1\), then that result to the nearest \(10^2\), …, finally to the nearest \(10^P\)). Note that when rounding a number with fewer than \(P\) digits, Bessie’s procedure always uses the most significant (and only) digit – so for example, rounding any one‐digit number \(a\) yields either \(0\) (if \(a<5\)) or \(10\) (if \(a\ge5\)).

Your task is to count how many integers \(x\) with \(2\le x\le N\) (\(1\le N\le 10^9\)) have \(f(x)\ne g(x)\). It turns out that the only discrepancies occur when the leading digit (the digit in the \(10^{P-1}\) place) is 4. In that case Bessie’s single‐step rounding always gives \(0\) while chain rounding may eventually carry enough to round up to \(10^P\). More precisely, if we write a \(P\)-digit number \(x\) with \(10^{P-1}\le x<10^P\) as \[ x = 4\times10^{P-1} + r, \quad 0\le r<10^{P-1}, \] then \(f(x)=0\) and it may be verified that g(x)=10^P if and only if, when regarding r as a \(P-1\)-digit string (with leading zeros allowed), at least one of the digits causes a carry in the chain rounding process. Equivalently, if we view the process digit–by–digit the discrepancy occurs exactly when not all of the \(P-1\) digits of \(r\) are in \(\{0,1,2,3,4\}\>.

More formally, if the numbers with leading digit 4 and \(P\) digits occur in the interval \[ 4\times10^{P-1} \le x \le 5\times10^{P-1}-1, \] then the total number of such numbers for which \(f(x)\ne g(x)\) is \[ 10^{P-1} - 5^{P-1} \quad \text{ (when the full block is within the range).} \]

For partial blocks at the boundary you should count only those numbers \(x\) with \(x\le N\) that satisfy the property.

Compute the total count of such numbers over all \(x\) with \(2\le x\le N\>.

inputFormat

The input consists of a single integer \(N\) (\(1\le N\le 10^9\)).

outputFormat

Output a single integer: the count of \(x\) with \(2\le x\le N\) for which Bessie’s rounding and Elsie’s chain rounding produce different results.

sample

50

5