Паліндромні числа#6288

Паліндромні числа

2 секунди

256 мегабайтів

Легка

Вася дуже захоплюється вивченням різних цікавих класів чисел. Сьогодні він досліджує паліндромні числа.

Вася вважає число паліндромним, якщо воно читається однаково зліва направо і справа наліво. При цьому, Вася дозволяє додавати до числа кілька (можливо жодного) лідируючих нулів. Наприклад, числа $22$ , $4554$ , $12321$ , $5050$ є паліндромними. Зокрема, до числа $5050$ можна додати один нуль, щоб отримати $05050$ , яке читається однаково з обох боків.

Серед інших, Васю цікавлять паліндромні числа, що відрізняються на $2$ . Для їх дослідження Вася розглядає такі $x$ , що $x - 1$ x-1 і $x + 1$ x+1 є паліндромними. Такі числа Вася називає міжпаліндромними. Вася хоче визначити кількість міжпаліндромних чисел $x$ від $L_{k}$ L_k до $R_{k}$ R_k включно для кількох відрізків $[L_{k}, R_{k}]$ [L_k, R_k].

Допоможіть Васі в цій нелегкій задачі!

Вхідні дані

Вхідний файл містить кілька відрізків, які цікавлять Васю. У першому рядку задано одне число $T$ ( $1 \leq T \leq 2000$ 1 \le T \le 2000) — кількість відрізків. У кожному з наступних $T$ рядків задано два числа $L_{k}$ L_k і $R_{k}$ R_k ( $1 \leq L_{k} \leq R_{k} \leq 1 0^{18}$ 1 \le L_k \le R_k \le 10^{18}) — межі відрізка.

Вихідні дані

Виведіть $T$ рядків. У $k$ -му рядку виведіть одне число — кількість міжпаліндромних чисел у відрізку від $L_{k}$ L_k до $R_{k}$ R_k включно.

Пояснення до прикладу: Від $17$ до $24$ паліндромними є числа $20$ і $22$ . Тому єдине міжпаліндромне число на відрізку $[18, 23]$ — це $21$ . У другому прикладі, число $21$ знову підходить. Від $49$ до $56$ паліндромними є числа $50$ , $55$ . Міжпаліндромних чисел на відрізку $[50, 55]$ немає.

Приклади

Приклад 1