题目描述

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$ 取模的结果。

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

提示

翻译由 DeepSeek V3.2 完成