No Equal Neighbouring Digits

Statement

Count the integers k with 1 <= k <= N in which no two neighbouring decimal digits are equal. For example 101 qualifies; 11 and 100 do not.

Input

One line with N.

Output

Print one integer: how many integers from 1 to N have no two equal neighbouring digits.

Constraints

1 <= N <= 10^18

Example 1

100

90

The nine numbers 11, 22, ..., 99 and the number 100 are excluded.

Example 2

9

9

Every single-digit number qualifies.