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

Обмеження: 2 сек., 512 МіБ

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

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

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

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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Обмеження

$1 \le n \le 10^9$.

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

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

• 18 балів: $n < 10$,

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

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4	5

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
14	10

Примітки

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