Reminder: in case of any technical issues, you can use the lightweight website
m1.codeforces.com,
m2.codeforces.com,
m3.codeforces.com.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Strange Functions

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet'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$$$.

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]$$$.

Example

Input

5 4 37 998244353 1000000007 12345678901337426966631415

Output

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)$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/01/2021 17:58:04 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|