Description

Given an integer $n$, find the number of ways to factor $n$ into a product of pairwise distinct integers each at least $2$. Output the answer modulo $998244353$.

Input Format

The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain an integer $n$, as described.

Output Format

Output $T$ lines, each containing a single integer, the answer.

1
688

6

Hint

In the sample, because

$688 = 2 \times 4 \times 86= 2 \times 8 \times 43= 2 \times 344= 4 \times 172= 8 \times 86= 16 \times 43$

the answer is $6$.

For $10\%$ of the testdata, $n$ is prime. For $20\%$ of the testdata, $2 \leq n \leq 10^4$. For $50\%$ of the testdata, $2 \leq n \leq 10^7$. For $100\%$ of the testdata, $2 \leq n \leq 10^{12}$. All testdata satisfy $1 \leq T \leq 5$.

Translated by ChatGPT 5