String Is Not That Easy

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

Input	Output
2 01 9	2 1