codeforces#P1455A. Strange Functions
Strange Functions
Description
Let's define a function $f(x)$ ($x$ is a positive integer) as follows: write all digits of the decimal representation of $x$ backwards, then get rid of the leading zeroes. For example, $f(321) = 123$, $f(120) = 21$, $f(1000000) = 1$, $f(111) = 111$.
Let's define another function $g(x) = \dfrac{x}{f(f(x))}$ ($x$ is a positive integer as well).
Your task is the following: for the given positive integer $n$, calculate the number of different values of $g(x)$ among all numbers $x$ such that $1 \le x \le n$.
The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.
Each test case consists of one line containing one integer $n$ ($1 \le n < 10^{100}$). This integer is given without leading zeroes.
For each test case, print one integer — the number of different values of the function $g(x)$, if $x$ can be any integer from $[1, n]$.
Input
The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.
Each test case consists of one line containing one integer $n$ ($1 \le n < 10^{100}$). This integer is given without leading zeroes.
Output
For each test case, print one integer — the number of different values of the function $g(x)$, if $x$ can be any integer from $[1, n]$.
Samples
5
4
37
998244353
1000000007
12345678901337426966631415
1
2
9
10
26
Note
Explanations for the two first test cases of the example:
- if $n = 4$, then for every integer $x$ such that $1 \le x \le n$, $\dfrac{x}{f(f(x))} = 1$;
- if $n = 37$, then for some integers $x$ such that $1 \le x \le n$, $\dfrac{x}{f(f(x))} = 1$ (for example, if $x = 23$, $f(f(x)) = 23$,$\dfrac{x}{f(f(x))} = 1$); and for other values of $x$, $\dfrac{x}{f(f(x))} = 10$ (for example, if $x = 30$, $f(f(x)) = 3$, $\dfrac{x}{f(f(x))} = 10$). So, there are two different values of $g(x)$.