题目描述

有 $n$ 个城市，第 $i$ 个城市有权值 $a_i$ ，初始所有城市间都没有边链接，你每次可以在两个城市 $u,v$ 间建一条双向边，花费的代价是 ${\max(a_u, a_v)}\choose{\min(a_u, a_v)}$ ，你需要用最小的代价，使得任意两个城市可以直接或间接通过道路连接。

注： $m \choose r$ 表示在 $m$ 个有标号元素中选择 $r$ 个的方案数，也就是组合数。

答案较大，你只需要输出最小花费在模 $998244353$ 意义下的值。

输入格式

第一行输入一个整数 $T$ 表示测试数据组数。

对于每组数据：

第一行输入一个整数 $n$ 。

接下来一行输入 $n$ 个整数 $a_1,a_2,…,a_n$ 。

$1 \le T \le 200$ 。

$1 \le n \le 2000,1 \le a_i \le 5000$ 。

输出格式

对于每组数据：

输出一行一个整数表示答案在模 $998244353$ 意义下的值。

样例

4
3
1 2 3
3
1 2 4
3
2 3 4
5
1 3 5 7 9

5
6
7
24