Champernowne 字符串是由按顺序连接正整数的十进制表示而形成的无限字符串。

它以 1234567891011121314... 开头。

可以证明，任何有限的数字字符串至少会在 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 取模。

样例

样例输入 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

样例输出 1

11
7
14
10
314159
796889014
7777
8058869
38886