Problem Statement

You are given an integer sequence $A$ of length $N$ and a positive integer $K$. You can perform the following operation on $A$ any number of times:

• Choose an integer $i$ with $1 \leq i \leq N-1$ such that $A_i + A_{i+1}$ is divisible by $K$, and swap $A_i$ and $A_{i+1}$.

Find the total number, modulo $998244353$, of distinct sequences that $A$ can become after performing the operation zero or more times.

Solve $T$ test cases per input.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq A_i \leq 10^9$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case $\mathrm{case}_t$ is given in the following format:

N K
A_1 A_2 \dots A_N

Output

Output the answers over a total of $T$ lines. The $t$-th line should contain the answer for the $t$-th test case.