{"raw_statement":[{"iden":"statement","content":"龙老师获得了一个不寻常的计算器，因为这个道具的品质是金色传说。它除了在按 $666$ 时可以发出声音以外，还可以输入一个算式并计算出它的结果。金色传说计算器的显示屏上只有 $n$ 个可以显示的位置，而且只有 $0 \\\\\\\\cdots 9$ 十个数字键和两个运算符键_+_、_-_共 $12$ 个按键可以按，连_=_都没有，所以必须输入一个 $n$ 位的合法算式，它才会自动计算出该算式的结果。\n\n我们定义合法的算式为一个*长度恰好为 $n$ 的字符串*，其中字符串只包含数字 $0 \\\\\\\\cdots 9$ 和运算符_+_、_-_，同时不允许算式第一个或最后一个位置出现运算符，也不允许同时有两个运算符相邻。算式的计算结果是对该字符串模拟十进制加减法运算得到的结果，只包含数字的算式其计算结果等于它本身。如果金色传说计算器的输入不是一个合法的算式，那么它就不能得到任何计算结果。例如，在 $n = 6$ 时，_1+2+3_、_+12345_、_23+45+_和_123+-4_都不是合法的算式，而_123456_和_0+0+00_都是合法的算式。注意，前导零是允许在算式中出现的。\n\n龙老师一个个地数出了计算器的显示位置数 $n$。他想知道，如果把所有的合法的算式全都都输入一次，金色传说计算器输出的所有计算结果之和是多少？计算结果的总和可能很大，请输出它对 $998244353$ 取模之后的答案。\n\n第一行输入一个正整数 $T \" \"(1 <= T <= 100)$，表示数据组数。\n\n接下来 $T$ 组数据，每组数据输入一个正整数 $n \" \"(1 <= n <= 5 times 10^5)$，表示金色传说计算器的显示位。\n\n对于每组数据，请输出一个非负整数，表示所有计算结果之和取模 $998244353$ 之后的答案，注意换行。\n\n当 $n = 1$ 时，共有 $0, 1, \\\\\\\\cdots, 9$ 共 $10$ 个合法算式，它们的结果之和是 $45$。\n\n当 $n = 2$ 时，共有 $00, \\\\\\\\cdots, 99$ 共 $100$ 个合法算式，它们的结果之和是 $4950$。\n\n当 $n = 3$ 时，$000, \\\\\\\\cdots, 999$ 是合法的算式，当然与形如_A+B_和_A-B_的算式也都是合法算式，它们的结果之和是 $500400$。\n\n"},{"iden":"input","content":"第一行输入一个正整数 $T \" \"(1 <= T <= 100)$，表示数据组数。接下来 $T$ 组数据，每组数据输入一个正整数 $n \" \"(1 <= n <= 5 times 10^5)$，表示金色传说计算器的显示位。"},{"iden":"output","content":"对于每组数据，请输出一个非负整数，表示所有计算结果之和取模 $998244353$ 之后的答案，注意换行。"},{"iden":"note","content":"当 $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$。"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the expression string.  \nLet $ \\Sigma = \\{0,1,\\dots,9,+,-\\} $ be the alphabet of 12 characters.  \nLet $ \\mathcal{L}_n \\subseteq \\Sigma^n $ be the set of *valid expressions* of length $ n $, defined as strings satisfying:  \n- No operator (`+` or `-`) at position 1 or $ n $.  \n- No two adjacent operators.  \n- Only digits and operators are used.  \n\nLet $ f(s) $ be the integer value obtained by evaluating the arithmetic expression $ s \\in \\mathcal{L}_n $ under standard left-to-right precedence (no parentheses, left-associative).  \n\n**Constraints**  \n$ 1 \\leq n \\leq 5 \\times 10^5 $, $ 1 \\leq T \\leq 100 $.  \n\n**Objective**  \nFor each $ n $, compute:  \n$$\n\\sum_{s \\in \\mathcal{L}_n} f(s) \\mod 998244353\n$$","simple_statement":"Given a calculator with exactly n display positions, you can input strings of length n using digits 0-9 and operators + or -, but the string must be valid: no operator at start or end, no two operators in a row. Calculate the sum of all possible valid expressions' results, modulo 998244353.","has_page_source":false}