405947: GYM102174 J 金色传说

龙老师获得了一个不寻常的计算器，因为这个道具的品质是金色传说。它除了在按 $$$666$$$ 时可以发出声音以外，还可以输入一个算式并计算出它的结果。金色传说计算器的显示屏上只有 $$$n$$$ 个可以显示的位置，而且只有 $$$0\cdots 9$$$ 十个数字键和两个运算符键+、-共 $$$12$$$ 个按键可以按，连=都没有，所以必须输入一个 $$$n$$$ 位的合法算式，它才会自动计算出该算式的结果。

我们定义合法的算式为一个长度恰好为 $$$n$$$ 的字符串，其中字符串只包含数字 $$$0\cdots 9$$$ 和运算符+、-，同时不允许算式第一个或最后一个位置出现运算符，也不允许同时有两个运算符相邻。算式的计算结果是对该字符串模拟十进制加减法运算得到的结果，只包含数字的算式其计算结果等于它本身。如果金色传说计算器的输入不是一个合法的算式，那么它就不能得到任何计算结果。例如，在 $$$n=6$$$ 时，1+2+3、+12345、23+45+和123+-4都不是合法的算式，而123456和0+0+00都是合法的算式。注意，前导零是允许在算式中出现的。

龙老师一个个地数出了计算器的显示位置数 $$$n$$$。他想知道，如果把所有的合法的算式全都都输入一次，金色传说计算器输出的所有计算结果之和是多少？计算结果的总和可能很大，请输出它对 $$$998244353$$$ 取模之后的答案。

第一行输入一个正整数 $$$T\ (1\le T\le 100)$$$，表示数据组数。

接下来 $$$T$$$ 组数据，每组数据输入一个正整数 $$$n\ (1\le n\le 5\times 10^5)$$$，表示金色传说计算器的显示位。

对于每组数据，请输出一个非负整数，表示所有计算结果之和取模 $$$998244353$$$ 之后的答案，注意换行。

5
1
2
3
4
5

45
4950
500400
50103000
19816235

当 $$$n=1$$$ 时，共有 $$$0,1,\cdots ,9$$$ 共 $$$10$$$ 个合法算式，它们的结果之和是 $$$45$$$。

当 $$$n=2$$$ 时，共有 $$$00,\cdots ,99$$$ 共 $$$100$$$ 个合法算式，它们的结果之和是 $$$4950$$$。

当 $$$n=3$$$ 时，$$$000,\cdots ,999$$$ 是合法的算式，当然与形如A+B和A-B的算式也都是合法算式，它们的结果之和是 $$$500400$$$。