Background

After going through countless hardships, Fusu finally arrived at the arcade. But she soon found that there was a huge line (not the NOi Qualifier’s Team B).

When there are many people, maimai players often decide who plays next by “queueing cards”. Because there are simply too many people, while queueing the cards, they noticed the ID numbers on the cards.

They asked Fusu a question. Can you solve it?

Problem Description

Fusu has a deque $a$. This deque is similar to the queue concept in computer science, but the difference is that it can read and pop elements from the front, and also read and pop elements from the back, so it is called a “double-ended queue (deque)”.

There are $n$ numbers in this deque. Fusu will construct a sequence $b$ of length $n$ through $n$ operations. In the $i$-th operation ($1 \leq i \leq n$), she can perform one of the following two processes:

1. Let $b_i$ be the front element of $a$, and pop one element from the front of $a$.
2. Let $b_i$ be the back element of $a$, and pop one element from the back of $a$.

We define the score of a pair $(i, j)$ as:

$$\mathrm{score}(i,j) = i^j \bmod 998244353$$

That is, the result of $i$ to the power of $j$ modulo $998244353$. In particular, in this problem we define $0^0 = 0$.

Now, Fusu wants to construct the sequence $b$ using the best strategy, to maximize the value of the following expression:

$$\sum_{i = 1}^{n - 1} \mathrm{score}(b_i, b_{i + 1})$$

That is, the sum of the scores of all adjacent pairs in $b$, computed in the original order.

Note that we only take modulo $998,244,353$ when computing the score of a pair. When computing the sum, we do not take the sum modulo anything.

Input Format

This problem contains multiple test cases in a single test file. The first line is a positive integer $T$, representing the number of test cases. For each test case:

The first line is an integer $n$ ($2 \leq n \leq 10^3$), representing the length of the sequence.
The second line contains $n$ integers $a_1, a_2, \dots a_n$ ($0 \leq a_i < 998,244,353$), representing the values in deque $a$ from front to back.

It is guaranteed that the sum of $n$ over all test cases in a single test file does not exceed $10^3$.

Output Format

For each test case, output one line with one integer representing the answer.

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

1168
15655

Hint

Translated by ChatGPT 5