CF2264E1.A Prime Flood (Easy Version)

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.

Antigun and Lamus have flooded Madamant's house. She wants them to make the water levels equal while removing as little water as possible.

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:

• 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.

Let $f(b)$ be the maximum integer $x$ such that, after some sequence of operations, every element of $b$ is equal to $x$.

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.

Each subsequence is considered independently, starting from its original values.

$^{\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.

这是本题的简单版本。两个版本的区别在于，在本版本中，$1 \le n \le 3000$。仅当您已解决本题的所有版本后，才可进行 Hack。

Antigun 和 Lamus 淹没了 Madamant 的房子。她希望他们通过移除尽可能少的水量，使各处水位相等。

形式化地，初始水位由数组 $a = [a_1, a_2, \ldots, a_n]$ 给出。对于每一次假想的清理操作，Antigun 和 Lamus 从 $a$ 中选取一个非空子序列$^{\text{∗}}$ $b$。他们可在 $b$ 上执行如下操作任意次（包括零次）：

• 选择一个质数 $p$；
• 同时将 $b$ 中所有当前值能被 $p$ 整除的元素 $b_i$ 减少 $1$；其余元素保持不变。

令 $f(b)$ 表示：经过若干次操作后，$b$ 中所有元素均可变为的最大整数 $x$。

请计算 $f(b)$ 对 $a$ 的所有非空子序列 $b$ 的求和结果，并对 $998\,244\,353$ 取模。即使两个子序列的元素值完全相同，只要它们由不同下标位置构成，即视为不同的子序列，需分别计数。

每个子序列均独立考虑，且均从其原始值开始操作。

$^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的子序列，当且仅当 $a$ 可通过从 $b$ 中删除若干（可能为零个或全部）任意位置的元素而得到。

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.

The first line of each test case contains a single integer $n$ ($1 \le n \le 3000$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 3000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3000$）—— 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）—— 数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $3000$。

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$ 取模。

In the first test case, the only non-empty subsequence is $[1]$, and no operation is needed. Therefore, its contribution is $f([1]) = 1$.

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$.

在第一个测试用例中，唯一的非空子序列为 $[1]$，且无需进行任何操作。因此，其贡献值为 $f([1]) = 1$。

在第二个测试用例中，所有仅包含数字 $4$ 的出现的 $2^3 - 1 = 7$ 个非空子序列，其贡献值为 $4 \cdot 7 = 28$；子序列 $[2]$ 的贡献值为 $2$；每个包含数字 $2$ 和至少一个 $4$ 的子序列均有 $f(b) = 1$，这样的子序列共 $7$ 个。因此，答案为 $28 + 2 + 7 = 37$。