P16083 [ICPC 2024 NAC] Champernowne Substring

Champernowne 字符串是一个无限字符串，由正整数按顺序的十进制表示拼接而成。 它的开头是 $ 1234567891011121314\ldots $ 可以证明，任何有限数字串至少会在 Champernowne 字符串中出现一次作为子串。 给定一个由数字和问号组成的字符串，请计算通过将每个问号替换为 $ 0 $ 到 $ 9 $ 之间的一个数字（每个问号可以替换成不同的数字）后，该字符串作为子串出现在 Champernowne 字符串中的最小可能起始下标。由于这个下标可能很大，请输出它对 $ 998{,}244{,}353 $ 取模的结果。

输入的第一行包含一个整数 $ t $（$ 1 \le t \le 10 $），表示测试用例的数量。 接下来的 $ t $ 行，每行包含一个字符串 $ s $（$ 1 \le |s| \le 25 $），由数字 $ 0 $ 到 $ 9 $ 或问号组成。

输出 $ t $ 行。对于每个测试用例，按顺序输出一行一个整数，表示该字符串作为子串出现在 Champernowne 字符串中的最小可能起始下标，对 $ 998{,}244{,}353 $ 取模的结果。

翻译由 DeepSeek V3.2 完成