You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小仓鼠李华在幼儿园就读期间跋涉坎坷之路，攀登崎岖之峰，以不屈之志与坚韧之心，跨越山海，终见曙光，最后凭借满 GPA 与数篇《超自然》杂志文章，获小仓鼠幼儿园“优秀学生奖学金-下界合金奖”。

因此，它打算用积木搭几条起伏的道路，以体现自己一路艰辛。这些积木路将在一块平地（初始平地上没有任何积木）上搭建，对于每条积木路：

长度为 $n$ 格，第 $i$ 格需要放置 $h_i$ 块积木（即目标高度）。积木的搭建遵循以下规则：第 $k$ 次可以选取一个合法区间 $[l_k,r_k]$，以消耗体力 $k \times (r_k - l_k + 1)$ 的代价，在区间上的每格放置 1 块积木。一个区间合法，当且仅当区间中每格的高度相同，且都小于目标高度。

李华作为脑力工作者，不想消耗太多体力，所以请你帮它求出：为了搭出每条积木路，最小的体力总消耗值。由于结果可能很大，请输出对 998244353 取模后的值。

Input

输入第一行：一个整数 $T$（$1 \le T \le 10$），表示想搭的积木路条数。

接下来 $2T$ 行：对于条积木路，第一行为一个正整数 $n$（$1\le n\le 10^6, 1\le T \times n\le 3 \times 10^6$），表示积木路的长度（格数）；第二行为 $n$ 个正整数 $h_i$（$0 \le h_i\leq 10^9$），表示第 $i$ 格的目标高度。

Output

输出 $T$ 行：每行一个整数，表示搭每条积木路所需的最小体力消耗（对 998244353 取模）。

Examples

Sample Input 1

3
10
8 9 9 9 7 6 6 6 4 3
10
2 10 9 8 6 10 5 4 3 2
10
9 0 10 10 1 9 8 1 7 7

Sample Output 1

278
265
843