{"raw_statement":[{"iden":"background","content":"经过千辛万苦，扶苏终于到达了机厅。但是她很快发现机厅排起了大 b 队 ~~（不是省选的 B 队）~~。\n\n舞萌玩家们在人多的时候经常采取排卡的方式决定谁下一个上机。因为人实在是太多了，他们在排卡的时候，便注意到了卡上的编号。\n\n他们向扶苏提了一个问题，你能解决吗？"},{"iden":"statement","content":"扶苏有一个双端队列 $a$。这个队列与计算机科学中队列的概念类似，不同的是，这个队列既可以从队列头读取和弹出元素，也可以在队列尾部读取和弹出元素，因此被称为『双端队列』。\n\n这个队列中有 $n$ 个数。扶苏将通过 $n$ 次操作构造一个长度为 $n$ 的序列 $b$，第 $i$（$1 \\leq i \\leq n$）次操作会可以进行如下两个过程之一：\n\n1. 令 $b_i$ 为 $a$ 的队列头，并在 $a$ 的头部弹出一个元素。\n2. 令 $b_i$ 为 $a$ 的队列尾，并在 $a$ 的尾部弹出一个元素。\n\n我们定义一个数对 $(i, j)$ 的得分为：\n\n$$\\mathrm{score}(i,j) = i^j \\bmod 998244353$$\n\n即 $i$ 的 $j$ 次幂对 $998244353$ 取余数的结果。特别的，在本题中我们规定 $0^0 = 0$。\n\n现在，扶苏想用最优的策略构造 $b$ 序列，最大化如下式子的值：\n\n$$\\sum_{i = 1}^{n - 1} \\mathrm{score}(b_i, b_{i + 1})$$\n\n即 $b$ 所有相邻两项按原顺序计算的得分之和。\n\n注意，我们仅在计算一个数对的时候将得分对 $998,244,353$ 取模，在计算求和时不再将这个和取余。"},{"iden":"input","content":"**本题单个测试点内有多组测试数据**。第一行是一个正整数，表示数据组数 $T$。对每组数据：\n\n第一行是一个整数 $n$（$2 \\leq n \\leq 10^3$），表示序列的长度。  \n第二行有 $n$ 个整数 $a_1, a_2, \\dots a_n$（$0 \\leq a_i < 998,244,353$），按从头到尾的顺序表示队列 $a$ 里每个数字的值。\n\n数据保证单个测试点内 $n$ 的和不超过 $10^3$。"},{"iden":"output","content":"对每组测试数据，输出一行一个整数表示答案。"}],"translated_statement":null,"sample_group":[["2\n5\n5 3 1 4 2\n6\n6 5 1 4 2 3","1168\n15655"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}