Description

Given a decimal positive integer N. Write from 1 to N for all integers, and then count the number of '1' which appears.

Input

input a single integer N (1 ≤ N ≤ 100000000)

Output

the number of '1'.

Sample

Input

1
2
10
15

Output

1
1
2
8

Source: modify from zjfu