Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

String Is Not That Easy

By YouKnowWho · Limits 6s, 512 MB

Let’s consider a string S which is obtained by concatenating the non-negative integers from 0 to 102000 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 ≤ 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


Discussion
Statistics

93% Solution Ratio

Alex.739685Earliest, 1M ago

Alex.739685Fastest, 0.0s

md_shajibLightest, 0 B

mdvirusShortest, 46B

Submit

Login to submit