题目描述

给定一个正整数 $N$，定义全1数 $R(k)$ 为 $k$ 个 $1$ 组成的数，即 $R(k) = \underbrace{111\ldots1}_{k \text{ 个 }}$。

请找到最大的正整数 $k$，使得 $R(k)$ 是 $N$ 的因子，并输出 $k$。

注意 $R(1) = 1$ 是所有正整数的因子，因此答案至少为 $1$。

输入格式

第一行有一个整数 $T$（$1 \le T \le 5 \times 10^5$），表示数据组数。接下来 $T$ 段，每段描述一组数据：

• 第一行包含一个正整数 $N$（$1 \le |N| \le 10^5$，其中 $|N|$ 表示 $N$ 的十进制位数；保证 $N$ 没有前导零）。

数据保证 $\sum |N| \le 5 \times 10^5$。

输出格式

对于每组数据，输出一行一个正整数 $k$。

3
1221
99
7

3
2
1

提示

在第一个样例中，$1221 = 111 \times 11$，所以 $R(3) = 111$ 是 $N$ 的因子。$R(4) = 1111$ 不是 $N$ 的因子，因此答案为 $3$。

在第二个样例中，$99 = 11 \times 9$，所以 $R(2) = 11$ 是 $N$ 的因子。$R(3) = 111 > 99$，因此答案为 $2$。

在第三个样例中，$7$ 不是 $11$ 的倍数，因此答案为 $1$。