Champernowne Substring

시간 제한10초메모리 제한2048 MB

요약

물음표가 섞인 숫자 문자열의 물음표를 적절한 숫자로 바꿔 샴퍼나운 문자열에 가장 앞선 위치에 나타나게 하고, 그 시작 인덱스를 998244353으로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 문자열, 수학, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

The Champernowne string is an infinite string formed by concatenating the base-10 representations of the positive integers in order.

It begins 1234567891011121314...

It can be proven that any finite string of digits will appear as a substring in the Champernowne string at least once.

Given a string of digits and question marks, compute the smallest possible index that this string could appear as a substring in the Champernowne string by replacing each question mark with a single digit from $0$ to $9$ . Each question mark can map to a different digit. Since this index can be large, print it modulo $998\\,244\\,353$ .

입력

The first line of input contains a single integer $t$ $(1 \leq t \leq 10)$ , which is the number of test cases.

Each of the next $t$ lines contains a string $s$ ( $1 \leq |s| \leq 25$ ) consisting of digits $0$ to $9$ or question marks.

출력

Output $t$ lines. For each test case in order, output a single line with a single integer, which is the smallest possible index where the string could appear as a substring in the Champernowne string, modulo $998\\,244\\,353$ .

예제1

예제 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

예상 출력