题目描述

给定一个多重集合 $a$，包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。你要通过如下过程构造一个新的多重集合 $s$：

1. 将 $a$ 划分为任意个非空的多重子集 $x_1,x_2,\dots,x_k$，且每个元素恰好属于其中一个 $x_i$。
2. 初始时 $s$ 为空。从每个 $x_i$ 中任选一个众数（即出现次数最多的元素；若有并列则这些元素都视为众数），将所选的众数插入到 $s$ 中（对每个 $x_i$ 选择一个众数并插入一个元素到 $s$）。

要求统计通过以上过程能得到的不同多重集合 $s$ 的个数，结果对 $998244353$ 取模。

注意：统计的是不同的多重集合（即不考虑元素顺序，但考虑元素的重复计数）。例如 $\{1,1,2\},\{1,2\},\{1,1,2,2\}$ 都被视为不同的多重集合。

输入格式

• 第一行包含一个整数 $t$，表示测试用例个数（$1\le t\le 5000$）。

• 对每个测试用例：

  • 第一行包含一个整数 $n$（$1\le n\le 5000$），表示多重集合 $a$ 的大小；
  • 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le n$），表示多重集合中的元素。

数据保证所有测试用例中 $n$ 的总和不超过 $5000$。

输出格式

对每个测试用例，输出一行，包含一个整数：

• 通过上述过程可以得到的不同多重集合 $s$ 的个数（对 $998244353$ 取模）。

样例输入

5
3
1 2 3
3
1 1 1
3
1 2 2
10
1 1 1 1 2 2 2 3 3 4
10
1 1 1 2 2 2 3 3 3 4

样例输出

7
3
4
111
126

说明

样例解释

• 第一个样例：元素互不相同，任意非空子集划分后每个块的众数就是该块唯一的元素，因此等价于选取任意非空子集，故共有 $2^3-1=7$ 种不同的多重集合 $s$。

• 第三个样例（$\{1,2,2\}$）可得出的 $s$ 有四种：

  • 将整个集合作为一个块 $\{1,2,2\}$，其众数为 $2$，得到 $\{2\}$；
  • 划分为 $\{1,2\}$ 与 $\{2\}$，分别选众数得到 $\{2,2\}$；
  • 划分为 $\{1\}$ 与 $\{2,2\}$，选众数得到 $\{1,2\}$；
  • 划分为 $\{1\},\{2\},\{2\}$，得到 $\{1,2,2\}$。