Problem Description

The Champernowne string is the infinite string formed by concatenating the decimal representations of the positive integers in order:

1234567891011121314...

It is known that every finite string of digits appears somewhere in this infinite string.

You are given a pattern string consisting of digits and question marks ?.
Each ? may be replaced independently by any one digit from 0 to 9.

For each test case, determine the smallest possible starting index at which the pattern can appear as a substring of the Champernowne string after replacing all question marks.

Because the answer can be very large, output it modulo 998244353.

Input

The first line contains an integer t (1 <= t <= 10), the number of test cases.

Each of the next t lines contains a string s (1 <= |s| <= 25) consisting only of digits and ?.

Output

For each test case, output one line containing a single integer: the minimum possible starting index where the pattern can appear in the Champernowne string, taken modulo 998244353.

Sample Input 1

9
0
???1
121
1?1?1
??5?54?50?5?505?65?5
000000000000
?2222222
?3????????9??8???????1??0
9?9??0????????????2

Sample Output 1

11
7
14
10
314159
796889014
7777
8058869
38886