Yet another substring problem

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The problem is completely unrelated to its problem code :).
Let us build an infinite string D that is simply a concatenation of the decimal representations of all positive integers without leading zeros. In other words, D = 12345678910111213141...
You are given a string S. Find the position of the first occurrence of S in D that satisfies one additional constraint: at least one integer that was concatenated to form D occurs entirely within S.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a string of digits S.
It is guaranteed that S will occur satisfying the given condition somewhere in D.
Output
For each test case, output a single line containing the minimal position number where S occurs in D under the given condition, modulo 10^{9}+7. Consider the string to be 1indexed: '1' is in position 1.
Constraints
 1 ≤ T ≤ 10
 1 ≤ S ≤ 300
 Subtask 1 (17 points): the answer won't exceed 10^{7}
 Subtask 2 (23 points): the answer will fit in a signed 64bit integer (before taking modulo).
 Subtask 3 (60 points): no additional constraints.
Example
Input: 2 78910 9930 Output: 7 2679
Explanation
Please pay attention that in the second test case the answer is not 788, as it may seem at first glance. This is because the part 298299300301 doesn't contain any integer completely in it  neither 299, nor 300. But the part 928929930931932 contains the integer 930 completely.
Author:  xcwgf666 
Tester:  white_king 
Editorial  http://discuss.codechef.com/problems/GRIDCONN 
Tags  biginteger, bruteforce, handling, ltime18, simple, xcwgf666 
Date Added:  11112014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 