Давайте определим функцию \(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\).
Выходные данные
Для набора входных данных выведите одно целое число — количество различных значений, которые может принимать \(g(x)\), если \(x\) может быть любым целым числом из \([1, n]\).
Примечание
Пояснения к двум первым наборам входных данных примера из условия:
- если \(n = 4\), то для каждого целого числа \(x\) такого, что \(1 \le x \le n\), \(\dfrac{x}{f(f(x))} = 1\);
- если \(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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
37
998244353
1000000007
12345678901337426966631415
|
1
2
9
10
26
|