D. GCD Counting
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array of length $$$n$$$ consisting of positive integers that do not exceed $$$m$$$.

You have $$$2^n - 1$$$ ways to choose a non-empty subsequence of the array.

For each $$$x \in [1, m]$$$, how many ways you can choose a non-empty subsequence $$$b$$$ of $$$a$$$ that:

$$$$$$ gcd(b_1, b_2, ...) = x $$$$$$

The greatest common divisor $$$gcd(a,b,c, \dots)$$$ of multiple positive integers is equal to the biggest integer $$$d$$$ such that all integers $$$a,b,c,\dots$$$ are divisible by $$$d$$$.

You have to print the answer for every $$$x$$$, since the answer could be huge, print the answer taken modulo $$$998244353$$$. If you get the same subsequence with different choices, they are considered to be different.

Input

The first line contains an integer $$$T(1 \le T \le 10^4)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n(1 \le n \le 10^6)$$$ and $$$m(1 \le m \le 10^6)$$$ — the length of the array and the limit of array elements.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n(1 \le a_i \le m)$$$ — the elements of the array.

It is guaranteed that $$$\sum n \le 10^6$$$ and $$$\sum m \le 10^6$$$ for all test cases.

Output

For each test case, print $$$m$$$ integers in a line, which is explained above.

Examples
Input
1
6 5
1 1 4 5 1 4
Output
59 0 0 3 1
Input
1
10 10
3 1 2 2 6 7 6 5 8 3
Output
978 27 12 0 1 3 1 1 0 0
Input
1
10 10
1 2 3 4 5 6 7 8 9 10
Output
983 26 5 2 2 1 1 1 1 1
Note

For the case in the first sample, there are $$$2^6 - 1 = 63$$$ ways to select a subsequence.

The only way to achieve $$$gcd=5$$$ is to choose subsequence $$$[5]$$$.

To achieve $$$gcd=4$$$, you can choose $$$[4]$$$ or $$$[4, 4]$$$, there are two ways to have $$$[4]$$$.

The rest subsequences have $$$gcd=1$$$.