# String Is Not That Easy

Contest Based on SUST Int...
Limits 6s, 512 MB

Let's consider a string $S$ which is obtained by concatenating the non-negative integers from 0 to $10^{2000}$ without leading zeroes and in increasing order.

So S = "0123456789101112131415…".

You are given another string $P$ containing digits from 0 to 9. You need to find the length of the largest substring of $P$ which is also a substring of $S$.

## Input

The first line will contain an integer $t$ ($1 ≤ t ≤ 50$), the number of test cases.

Each of the next t lines will contain a string $P$ ($1 ≤ \texttt{length of P} ≤ 2000$) containing digits from 0 to 9. Note that $P$ can contain leading zeroes.

## Output

Output the length of the largest substring of $P$ which is also a substring of $S$.

## Sample

InputOutput
2
01
9

2
1