You are given four integers a, d, K, and N. Consider N numbers, \(b_1, b_2, ...\ , b_N\) where \(b_i = a + (i - 1) \times d\). Your task is to evaluate the following sum:

• \(\sum\limits_{v_1 \geq 0, v_2 \geq 0, .., v_N \geq 0 \\ v_1 + v_2 + .. + v_N = k} \left(\prod\limits_{i=1}^{N} b_i^{v_i}\right)\) for each k = 0, 1, 2,... , K

Since the sum can be very large, you are required to print it modulo \(998244353\).

Note: The sum is over all ordered tuples \((v_1, v_2, ...\ , v_N)\) satisfying \(\sum\limits_{i=1}^{N} v_i = k\).

Input format

• The first line contains a single integer T denoting the number of test cases.
• The first line of each test case contains four space-separated integers a, d, K, and N.

Output format

For each test case (in a separate line), print K + 1 space-separated integers in a new line denoting the sum for each k = 0, 1, 2, .. ,K. Print the output modulo \(998244353\).

Constraints

\(1 \leq T \leq 1000 \\ 1 \leq a, d, N < 998244353 \\ 1 \leq K \leq 5 \times 10^5 \\ \text{Sum of K over all test cases does not exceed } 10^6\)