[yLCPC2024] D. 排卡

经过千辛万苦，扶苏终于到达了机厅。但是她很快发现机厅排起了大 b 队 ~~（不是省选的 B 队）~~。 舞萌玩家们在人多的时候经常采取排卡的方式决定谁下一个上机。因为人实在是太多了，他们在排卡的时候，便注意到了卡上的编号。 他们向扶苏提了一个问题，你能解决吗？

扶苏有一个双端队列 $a$。这个队列与计算机科学中队列的概念类似，不同的是，这个队列既可以从队列头读取和弹出元素，也可以在队列尾部读取和弹出元素，因此被称为『双端队列』。 这个队列中有 $n$ 个数。扶苏将通过 $n$ 次操作构造一个长度为 $n$ 的序列 $b$，第 $i$（$1 \leq i \leq n$）次操作会可以进行如下两个过程之一： 1. 令 $b_i$ 为 $a$ 的队列头，并在 $a$ 的头部弹出一个元素。 2. 令 $b_i$ 为 $a$ 的队列尾，并在 $a$ 的尾部弹出一个元素。 我们定义一个数对 $(i, j)$ 的得分为： $$\mathrm{score}(i,j) = i^j \bmod 998244353$$ 即 $i$ 的 $j$ 次幂对 $998244353$ 取余数的结果。特别的，在本题中我们规定 $0^0 = 0$。 现在，扶苏想用最优的策略构造 $b$ 序列，最大化如下式子的值： $$\sum_{i = 1}^{n - 1} \mathrm{score}(b_i, b_{i + 1})$$ 即 $b$ 所有相邻两项按原顺序计算的得分之和。 注意，我们仅在计算一个数对的时候将得分对 $998,244,353$ 取模，在计算求和时不再将这个和取余。

**本题单个测试点内有多组测试数据**。第一行是一个正整数，表示数据组数 $T$。对每组数据： 第一行是一个整数 $n$（$2 \leq n \leq 10^3$），表示序列的长度。 第二行有 $n$ 个整数 $a_1, a_2, \dots a_n$（$0 \leq a_i < 998,244,353$），按从头到尾的顺序表示队列 $a$ 里每个数字的值。 数据保证单个测试点内 $n$ 的和不超过 $10^3$。

对每组测试数据，输出一行一个整数表示答案。

2
5
5 3 1 4 2
6
6 5 1 4 2 3

1168
15655