Дивна шеренга

Limits: 2 sec., 512 MiB

На фермі Зеника та Марічки є дуже багато жеребців. Кожен жеребець на шиї має табличку з однією цифрою від 0 до 9.

Зеник з Марічкою хочуть вишикувати коней у шеренгу.

Назвемо десятковою шеренгою для невід’ємного цілого числа \(m\) шеренгу коней, де цифри на табличках на шиях коней зліва направо утворюють десятковий запис числа \(m\). У десятковій шерензі перший кінь може мати на шиї табличку із цифрою 0 лише в одному випадку — якщо це шеренга для \(m=0\).

Назвемо десяткову шеренгу дивною, якщо одночасно виконуються такі умови:

• усі коні в шерензі мають різні цифри на своїх табличках,

• цифри на табличках коней у шерензі утворюють паліндром, тобто читаються однаково зліва направо та справа наліво.

Наприклад, десяткова шеренга 6 є дивною, тому що читається однаково в двох напрямках, а також жодна цифра не повторюється. Десяткова шеренга 123 не є дивною, тому що читається по-різному зліва направо (123) та справа наліво (321). Десяткова шеренга 474 не є дивною, тому що в ній повторюється цифра 4 двічі.

Для заданого цілого числа \(n\) порахуйте кількість чисел \(0 \le m \le n\), для яких десяткова шеренга є дивною.

Input

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

Output

Виведіть ціле число — кількість чисел від \(0\) до \(n\), для яких десяткова шеренга є дивною.

Constraints

\(1 \le n \le 10^9\).

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 18 балів: \(n < 10\),

• 40 балів: \(n \le 1000\),

• 40 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Samples

Input (stdin) сopy	Output (stdout) сopy
4	5

Input (stdin) сopy	Output (stdout) сopy
14	10

Notes

У першому прикладі \(n=4\). Для цього прикладу є п’ять дивних десяткових шеренг: 0, 1, 2, 3, 4.