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 <= T <= 100)$，表示数据组数。 接下来 $T$ 组数据，每组数据输入一个正整数 $n " "(1 <= n <= 5 times 10^5)$，表示金色传说计算器的显示位。 对于每组数据，请输出一个非负整数，表示所有计算结果之和取模 $998244353$ 之后的答案，注意换行。 当 $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$。 ## Input 第一行输入一个正整数 $T " "(1 <= T <= 100)$，表示数据组数。接下来 $T$ 组数据，每组数据输入一个正整数 $n " "(1 <= n <= 5 times 10^5)$，表示金色传说计算器的显示位。 ## Output 对于每组数据，请输出一个非负整数，表示所有计算结果之和取模 $998244353$ 之后的答案，注意换行。 [samples] ## Note 当 $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$。