A. Странные функции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Давайте определим функцию $$$f(x)$$$ ($$$x$$$ — положительное целое число) следующим образом: запишем все цифры десятичного представления $$$x$$$ в обратном порядке, а затем избавимся от лидирующих нулей. Например, $$$f(321) = 123$$$, $$$f(120) = 21$$$, $$$f(1000000) = 1$$$, $$$f(111) = 111$$$.

Давайте определим другую функцию $$$g(x) = \dfrac{x}{f(f(x))}$$$ ($$$x$$$ — положительное целое число).

Ваша задача состоит в следующем: для данного положительного целого числа $$$n$$$ вычислите количество различных значений $$$g(x)$$$ среди всех чисел $$$x$$$ таких, что $$$1 \le x \le n$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Каждый набор состоит из одной строки, содержащей одно целое число $$$n$$$ ($$$1 \le n < 10^{100}$$$). Это целое число задается без лидирующих нулей.

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

Для набора входных данных выведите одно целое число — количество различных значений, которые может принимать $$$g(x)$$$, если $$$x$$$ может быть любым целым числом из $$$[1, n]$$$.

Пример
Входные данные
5
4
37
998244353
1000000007
12345678901337426966631415
Выходные данные
1
2
9
10
26
Примечание

Пояснения к двум первым наборам входных данных примера из условия:

  1. если $$$n = 4$$$, то для каждого целого числа $$$x$$$ такого, что $$$1 \le x \le n$$$, $$$\dfrac{x}{f(f(x))} = 1$$$;
  2. если $$$n = 37$$$, то для некоторых целых чисел $$$x$$$ таких, что $$$1 \le x \le n$$$, $$$\dfrac{x}{f(f(x))} = 1$$$ (например, если $$$x = 23$$$, $$$f(f(x)) = 23$$$,$$$\dfrac{x}{f(f(x))} = 1$$$); а для других значений $$$x$$$, $$$\dfrac{x}{f(f(x))} = 10$$$ (например, если $$$x = 30$$$, $$$f(f(x)) = 3$$$, $$$\dfrac{x}{f(f(x))} = 10$$$). Итак, существуют два различных значения $$$g(x)$$$.