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

Обмеження: 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.