C. Map1e
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a positive integer $$$N$$$, define the repunit $$$R(k)$$$ as the number consisting of $$$k$$$ ones, i.e., $$$R(k) = \underbrace{11\ldots1}_{k}$$$.

Find the largest positive integer $$$k$$$ such that $$$R(k)$$$ is a divisor of $$$N$$$, and output $$$k$$$.

Note that $$$R(1) = 1$$$ divides every positive integer, so the answer is at least $$$1$$$.

Input

The first line contains a positive integer $$$T$$$ — the number of test cases.

The next $$$T$$$ lines each contain a positive integer $$$N$$$ (with no leading zeros).

$$$1 \le T \le 5 \times 10^5$$$, $$$1 \le |N| \le 10^5$$$, $$$\sum |N| \le 5 \times 10^5$$$, where $$$|N|$$$ denotes the number of decimal digits of $$$N$$$.

Output

Output $$$T$$$ lines, each containing a positive integer $$$k$$$.

Example
Input
3
1221
99
7
Output
3
2
1
Note

In the first example, $$$1221 = 111 \times 11$$$, so $$$R(3) = 111$$$ divides $$$N$$$. $$$R(4) = 1111$$$ does not divide $$$N$$$, so the answer is $$$3$$$.

In the second example, $$$99 = 11 \times 9$$$, so $$$R(2) = 11$$$ divides $$$N$$$. $$$R(3) = 111 \gt 99$$$, so the answer is $$$2$$$.

In the third example, $$$7$$$ is not a multiple of $$$11$$$, so the answer is $$$1$$$.