You are given a number n.

Find the number of occurrences of the digit 1 in all numbers less than or equal to n.

Say n = 15.

1 occurs in 1, 10, 11, 12, 13, 14 and 15.

That is a total of 8 ones (since 11 has two 1s).

Hence, the output is 8.

Input:

n - an integer

Output:

The number of occurrences of 1 in all numbers less than or equal to n.

Constraints:

1 <= n <= 10^9