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


94% Solution Ratio

Alex.739685Earliest, Dec '19

Alex.739685Fastest, 0.0s

md_shajibLightest, 0 B

bokaifShortest, 42B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.