Сусідні цифри – різні

Limits: 2 sec., 256 MiB

Марічку цікавить, скільки є натуральних чисел строго менших за \(n\) таких, що не мають двох сусідніх однакових цифр у десятковому записі.

Допоможіть Зенику порахувати цю кількість для Марічки.

Input

У єдиному рядку задано одне ціле число \(n\).

Output

У єдиному рядку виведіть одне ціле число — відповідь на задачу.

Constraints

\(1 \le n \le 10^{18}\).

Samples

Input (stdin) сopy	Output (stdout) сopy
47	42

Input (stdin) сopy	Output (stdout) сopy
7474	5575

Notes

У першому прикладі підходять усі числа від 1 до 46 включно, окрім 11, 22, 33 та 44.