| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 (추가 시간 없음) | 2048 MB (추가 메모리 없음) | 72 | 23 | 17 | 35.417% |
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円$.
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
11 7 14 10 314159 796889014 7777 8058869 38886