Problem Description

Given a positive integer $N$, define the repunit number $R(k)$ as the number consisting of $k$ digits of $1$, that is, $R(k) = \underbrace{111\ldots1}_{k \text{ digits }}$.

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

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

Input Format

The first line contains an integer $T$ ($1 \le T \le 5 \times 10^5$), representing the number of test cases. Then follow $T$ blocks, each describing one test case:

• The first line contains a positive integer $N$ ($1 \le |N| \le 10^5$, where $|N|$ denotes the number of decimal digits of $N$; it is guaranteed that $N$ has no leading zeros).

It is guaranteed that $\sum |N| \le 5 \times 10^5$.

Output Format

For each test case, output one positive integer $k$ per line.

3
1221
99
7

3
2
1

Hint

In the first sample, $1221 = 111 \times 11$, so $R(3) = 111$ is a divisor of $N$. $R(4) = 1111$ is not a divisor of $N$, so the answer is $3$.

In the second sample, $99 = 11 \times 9$, so $R(2) = 11$ is a divisor of $N$. $R(3) = 111 > 99$, so the answer is $2$.

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

Translated by ChatGPT 5