Déjà vu

For a subsequence $b$, $f(b)$ retains exactly the prime powers whose exponents are equal in every chosen element. For example, $12=2^2\cdot3$ and $20=2^2\cdot5$ retain only $2^2$, giving $f((12,20))=4$.

Write $d\parallel x$ if $d\mid x$ and $\gcd(d,x/d)=1$. Such a divisor is obtained by keeping or discarding each entire prime-power factor of . Let and compute . Count the frequency of each value and enumerate all subset products of its prime-power factors.

Let $E_d$ count subsequences with $f(b)=d$. Initialize $E_d=2^{c_d}-1$. Process , subtracting from for every with . The answer is

$$\sum_{d=1}^{A}dE_d,$$

with all calculations performed modulo $998\,244\,353$.

Precomputing smallest prime factors and powers of $2$ gives $O(N+A\log A)$ time and $O(N+A)$ space per case.

Proof

After $r$ operations choosing a prime $p$, an exponent $e_i$ becomes $\max(e_i-r,0)$. Equal exponents are best left unchanged. Unequal exponents can become equal only when all reach zero. Hence retains exactly the positive prime powers shared with identical exponents by all chosen elements.