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.
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.
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 the length of the largest substring of P which is also a substring of S.
2 01 9