质数洪水（简单版）AI (CI翻译)
This is the Easy version of the problem. The difference between the versions is that in this version, $1 \le n \le 3000$. You can hack only if you solved all versions of this problem.
这是本题的简单版。不同版本之间的区别在于，本版本中 $1 \le n \le 3000$。只有解决了本题的所有版本，你才能进行 hack。AI (CI翻译)
Antigun and Lamus have flooded Madamant's house. She wants them to make the water levels equal while removing as little water as possible.
Antigun 和 Lamus 把 Madamant 的房子淹了。她希望他们在尽可能少排水的前提下，使各处的水位相等。AI (CI翻译)
Formally, the initial water levels are given by an array $a = [a_1, a_2, \ldots, a_n]$. For each hypothetical cleanup, Antigun and Lamus select a non-empty subsequence$^{\text{∗}}$ $b$ of $a$. They may perform the following operation on $b$ any number of times, possibly zero:
形式化地，初始水位由数组 $a = [a_1, a_2, \ldots, a_n]$ 给出。对于每一种假设的清理方案，Antigun 和 Lamus 会从 $a$ 中选择一个非空子序列$^{\text{∗}}$ $b$。他们可以对 $b$ 执行任意次以下操作，也可以不执行任何操作：AI (CI翻译)
- choose a prime number
$p$; - simultaneously decrease every element
$b_i$whose current value is divisible by$p$by$1$. All other elements remain unchanged.
- 选择一个质数
$p$； - 将所有当前值能被
$p$整除的元素$b_i$同时减去$1$。其他元素保持不变。
Let $f(b)$ be the maximum integer $x$ such that, after some sequence of operations, every element of $b$ is equal to $x$.
设 $f(b)$ 为满足以下条件的最大整数 $x$：经过若干次操作后，$b$ 中的所有元素都等于 $x$。AI (CI翻译)
Find the sum of $f(b)$ over all non-empty subsequences $b$ of $a$, modulo $998\,244\,353$. Subsequences formed by different choices of indices are counted separately, even if their values are equal.
求 $a$ 的所有非空子序列 $b$ 的 $f(b)$ 之和，对 $998\,244\,353$ 取模。通过不同下标选择得到的子序列，即使其元素值相同，也要分别计数。AI (CI翻译)
Each subsequence is considered independently, starting from its original values.
每个子序列都独立考虑，且均从其原始元素值开始操作。AI (CI翻译)
$^{\text{∗}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements from arbitrary positions.
$^{\text{∗}}$如果序列 $a$ 可以通过从序列 $b$ 的任意位置删除若干个元素（可以不删除，也可以全部删除）得到，则称 $a$ 是 $b$ 的一个子序列。AI (CI翻译)
Input
输入格式
AI (CI翻译)Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 3000$). The description of the test cases follows.
每个测试包含多组测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 3000$）。接下来是各组测试用例的描述。AI (CI翻译)
The first line of each test case contains a single integer $n$ ($1 \le n \le 3000$) — the length of the array $a$.
每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 3000$）——数组 $a$ 的长度。AI (CI翻译)
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of $a$.
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——数组 $a$ 的元素。AI (CI翻译)
It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$.
保证所有测试用例的 $n$ 之和不超过 $3000$。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each test case, print one integer — the sum of $f(b)$ over all non-empty subsequences $b$ of $a$, modulo $998\,244\,353$.
对于每组测试用例，输出一个整数——$a$ 的所有非空子序列 $b$ 的 $f(b)$ 之和，对 $998\,244\,353$ 取模。AI (CI翻译)
Note
说明
AI (CI翻译)In the first test case, the only non-empty subsequence is $[1]$, and no operation is needed. Therefore, its contribution is $f([1]) = 1$.
在第一组测试用例中，唯一的非空子序列是 $[1]$，不需要执行任何操作。因此，它的贡献为 $f([1]) = 1$。AI (CI翻译)
In the second test case, the $2^3 - 1 = 7$ non-empty subsequences containing only occurrences of $4$ contribute $4 \cdot 7 = 28$. The subsequence $[2]$ contributes $2$. Each of the $7$ subsequences containing the value $2$ and at least one occurrence of $4$ has $f(b) = 1$. Hence, the answer is $28 + 2 + 7 = 37$.
在第二组测试用例中，仅包含 $4$ 的 $2^3 - 1 = 7$ 个非空子序列的贡献为 $4 \cdot 7 = 28$。子序列 $[2]$ 的贡献为 $2$。对于包含值 $2$ 且至少包含一个 $4$ 的 $7$ 个子序列中的每一个，都有 $f(b) = 1$。因此，答案为 $28 + 2 + 7 = 37$。AI (CI翻译)
样例
4
1
1
4
2 4 4 4
4
2 3 4 4
6
3 6 1 1 1 1
1
37
34
72
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。