P16913 [JLCPC 2026] Map1e

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$.

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$.

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

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