题目描述

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

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

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

输入格式

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

对于每组数据：

第一行输入一个整数 \(n\)。

接下来一行输入 \(n\) 个整数 \(a_1, a_2, \dots, 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