F. Числа и строки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для каждого целого числа $$$x$$$ от $$$1$$$ до $$$n$$$ сформируем строку $$$S(x)$$$ по следующим правилам:

  • вычислим $$$(x+1)$$$;
  • запишем $$$x$$$ и $$$x+1$$$ друг за другом в десятичной системе без разделителей и ведущих нулей;
  • в получившейся строке отсортируем все цифры по неубыванию.

Например, строка $$$S(139)$$$ — это 011349 (до сортировки цифр будет 139140). Строка $$$S(99)$$$ — это 00199.

Ваша задача — посчитать количество различных строк среди $$$S(1), S(2), \dots, S(n)$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей единственное число $$$n$$$ ($$$1 \le n \le 10^{9} - 2$$$).

Выходные данные

На каждый набор входных данных выведите одно целое число — количество различных строк среди $$$S(1), S(2), \dots, S(n)$$$.

Пример
Входные данные
2
42
1337
Выходные данные
42
948