String Is Not That Easy

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

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

So S = "0123456789101112131415…".

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

Input

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

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

Output

Output the length of the largest substring of PP which is also a substring of SS.

Sample

InputOutput
2
01
9
2
1

Submit

Login to submit.

Statistics

95% Solution Ratio
Alex.739685Earliest, Dec '19
Alex.739685Fastest, 0.0s
md_shajibLightest, 0 B
Nusab19Shortest, 39B
Toph uses cookies. By continuing you agree to our Cookie Policy.