You’ll be given an array of $N$ integers and two more integers $K$ and $M$. You have to find the number of lcm divisible subsequence of length $M$ in that array.

A subsequence of length $M$ is called lcm divisible subsequence if the LCM (Lowest Common Multiple) of all the numbers in that subsequence is divisible by $K$. For example, if $A = [2, 2, 3, 4, 7, 6]$, $M = 3$ and $K = 6$, then $(2, 2, 6)$ is a valid lcm divisible subsequence. Because the length of this subsequence is $M = 3$ and the LCM is $6$, which is divisible by $K = 6$.

Note: A subsequence in the array $A$ is a sequence that can be derived by deleting some or no elements without changing the order of the remaining elements in the array $A$. Two subsequences are considered different if the chosen indices are different.

Constraints

$1 \leq T \leq 5 $ $1 \leq N \leq 100000 $ $1 \leq M \leq 1000 $ $1 \leq K, A_i \leq 50000 $

Input

The first line of the input contains a single integer $T$ denoting the number of test cases, then $T$ test cases follow. The first line of a test case contains three integers $N$, $M$ and $K$. The following line of the test case contains $N$ space separated integers of the array $A$.

Output

For each test case print a single integer, the number of lcm divisible subsequence in the given array. Since the answer can be quite large, you have to compute it modulo $998244353$.