该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

“我看伦敦未必有神社忧郁”——博丽灵梦&东风谷早苗

$\hspace{15pt}$雾之湖的冰之妖精琪露诺，在最近的数学课上发现了一个让她极其愤怒的事实：明明 $9$ 才是幻想乡最强、理应最大的数字，但人类只要在随便哪个微不足道的数字后面加上一个 $0$（比如把 $1$ 变成 $10$），居然就能轻易反超 $9$ ！这说明 $0$ 拥有让数字无限膨胀的可怕力量。

$\hspace{15pt}$“不可原谅！为了保住 $9$ 的最强地位，只要把所有带 $0$ 的数字都冻起来不能用就好了！”

$\hspace{15pt}$于是，琪露诺发动了极寒魔法，将整个幻想乡中所有包含 $0$ 的数字全部冻结。从那一刻起，无论账本、日历还是页码，任何带有 $0$ 的数字都变成了一块坚冰，彻底从计数体系中消失了。

$\hspace{15pt}$与此同时，博丽神社的巫女博丽灵梦打开了赛钱箱，看着里面少得可怜的几张香客留下的金额单据，陷入了沉思。由于带 $0$ 的数字被剔除，幻想乡的“货币面值”发生了剧变。比如，一张原本写着 $23$ 元的单据，因为前面少了 $10$ 、$20$ 等数字，在这个新体系里其实只排在第 $21$ 位——也就是说，它实际可能只值 $21$ 元了！

$\hspace{15pt}$灵梦是一个非常现实的巫女。如果这次异变导致她的赛钱大幅缩水，她绝对会立刻抄起御币，飞奔去雾之湖把那个笨蛋妖精狠狠退治一顿；但若是算下来的结果不但没亏，反而还赚了……那么将无事发生，幻想乡一如既往地迎来了和平的一天。

$\hspace{15pt}$为了决定到底要不要去解决这次异变，灵梦必须先算清楚，单据上那些没有被冻结的数字，在新法则下到底变成了多少钱（即在新序列中的真实排位）。现在，她需要你的帮助。

$\hspace{15pt}$在琪露诺的魔法影响下，任何包含字符 $0$ 的数字都已被冻结无法使用。幻想乡的居民们现在只能被迫使用 $1 \sim 9$ 这 $9$ 个数字来从小到大计数。

$\hspace{15pt}$在这个全新的计数法则下，新序列的前几项依次是： $1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, \dots, 19, 21, \dots, 99, 111, 112 \dots$

$\hspace{15pt}$（注意：原本的 $10$, $20$, $101$ 等数字因为包含 $0$，已经全部被冻结剔除。）

$\hspace{15pt}$现在，灵梦会给你一张单据上的金额 $S$（保证是一个在异变后未被冻结的合法数字串，即不包含字符 $0$）。 $\hspace{15pt}$请你帮灵梦计算出：在异世界的全新计数序列中，这个数字 $S$ 恰好排在第几个（即它异变后的真实价值是多少）？

$\hspace{15pt}$由于幻想乡的土豪香客可能随手写下了一个极长的金额，答案可能会非常大，请将计算出的真实价值对 $998244353$ 取模后输出。

Input

$\hspace{15pt}$第一行包含一个整数 $T$，表示需要处理的单据金额个数（即测试用例组数）。 $\hspace{15pt}$接下来 $T$ 行，每行包含一个仅由数字 $1 \sim 9$ 组成的字符串 $S$。

Output

$\hspace{15pt}$对于每组测试数据，输出一行一个整数，表示该金额在灵梦的新序列中的排位编号（真实价值），结果对 $998244353$ 取模。

3
9
11
23

9
10
21

Constraints

$\hspace{15pt}$对于全部测试数据，保证：

$\hspace{15pt} 1 \le T \le 20$

$\hspace{15pt} 1 \le |S| \le 10^5$

$\hspace{15pt} \sum |S| \le 10^5$

$\hspace{15pt}$字符串 $S$ 仅由字符 $1$ 到 $9$ 组成。