P16083 [ICPC 2024 NAC] Champernowne Substring

The Champernowne string is an infinite string formed by concatenating the base-10 representations of the positive integers in order. It begins $ 1234567891011121314\ldots $ 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 \le t \le 10 $), which is the number of test cases. Each of the next $ t $ lines contains a string $ s $ ($ 1 \le |s| \le 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 $.