给定一个正整数 $N$，定义全1数（repunit）$R(k)$ 为由 $k$ 个 1 组成的数，即：

$$R(k) = \underbrace{11\dots1}_{k}$$

求出最大的正整数 $k$，使得 $R(k)$ 是 $N$ 的约数，并输出 $k$。

注意，$R(1) = 1$ 整除每个正整数，因此答案至少为 1。

输入格式

第一行包含一个正整数 $T$ — 测试用例的数量。

接下来的 $T$ 行，每行包含一个正整数 $N$（不含前导零）。

$1 \le T \le 5 \times 10^5$，$1 \le |N| \le 10^5$，$\sum |N| \le 5 \times 10^5$，其中 $|N|$ 表示 $N$ 的十进制位数。

输出格式

输出 $T$ 行，每行包含一个正整数 $k$。

样例

输入样例 1

3
1221
99
7

输出样例 1

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。