Déjà vu

You are given an array $a=(a_1,a_2,\ldots,a_N)$ of positive integers.

Choose one or more elements, keeping their original order, to form a subsequence $b$. You may perform the following operation on the chosen subsequence any number of times.

1. Choose a prime number $p$.
2. Simultaneously divide every current element of $b$ that is divisible by $p$ by $p$. Leave all other elements unchanged.

For example, choosing $p=2$ for $b=(6,10,9)$ changes it to $(3,5,9)$. You cannot divide only the while leaving the unchanged: you cannot choose which divisible elements are affected.

Use these operations to make all elements of $b$ equal. Let $f(b)$ be the largest common value that can be obtained. Performing no operations is allowed, and making every element equal to $1$ is always possible.

For example, if $b=(12,20)$, choosing $p=3$ gives $(4,20)$, and then choosing $p=5$ gives . The largest attainable common value is , so . For a subsequence with one element, performing no operations is optimal, so .

Find the sum of $f(b)$ over all nonempty subsequences $b$, modulo $998\ 244\ 353$.

Each subsequence starts independently from the original values. Operations on one subsequence do not affect any other subsequence. Subsequences chosen from different sets of indices are counted separately, even if their values are identical. For example, the array $a=(2,2)$ has three nonempty subsequences: $(2)$ using the first index, $(2)$ using the second index, and $(2,2)$ using both indices.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print the sum of $f(b)$ over all nonempty subsequences $b$, modulo $998\ 244\ 353$, on its own line.

For each test case, let $A=\max(a_1,a_2,\ldots,a_N)$.