题目背景

经过千辛万苦，扶苏终于到达了机厅。但是她很快发现机厅排起了大 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