本题我是暴力做的……就没有算法分类了。

下面是题目复述：

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)=xf(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≤x≤n.

Input

The first line contains one integer t (1≤t≤100) — the number of test cases.

Each test case consists of one line containing one integer n (1≤n<10100). 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≤x≤n, xf(f(x))=1;

if n=37, then for some integers x such that 1≤x≤n, xf(f(x))=1 (for example, if x=23, f(f(x))=23,xf(f(x))=1); and for other values of x, xf(f(x))=10 (for example, if x=30, f(f(x))=3, xf(f(x))=10). So, there are two different values of g(x).

下面是解题思路：

我们从注释入手，不难发现如果输入询问的是一位数，那么答案只有1，如果是两位数，那么有10，1……以此类推，我们得到答案。

下面是AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
const int N=110;
using namespace std;

char s[N];
int main()
{
    int t;
    scanf("%d",&t);
    getchar();
    while (t--)
    {
         cin.getline(s,N);
         int len=strlen(s);
         printf("%d\n",len);
    }
    return 0;
}