Jini and the One

Limits 1s, 512 MB

Jini’s favorite number is one. She always looks for one in any number and if she finds the digit 1 in a number then she considers that this is a lucky number. Now counting till a large number while finding numbers that have digit 1 at least once in them can be hard for her. Thus she needs your help.

Given $N$ can you find her how many numbers from $1$ to $N$ contain digit $1$ at least once?

Input

The input contains a single integer $N$where $1≤N≤10^{6}$

Output

Print an Integer that indicates number of integers that has digit $1$ at least once.

Samples

InputOutput
19
11
InputOutput
23
12

In the first example, $N = 19$ so the answer will be $11$ since $1,10,11,12,13,14,15,16,17,18,19$ are the numbers that have digit $1$ in them at least once.