Давайте определим функцию \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач