Problem Description

Given $n,\,a,\,b,\,c$, compute respectively $\sum\limits_{i=0}^{n}\left\lfloor \frac{ai+b}{c} \right\rfloor$, $\sum\limits_{i=0}^{n}{\left\lfloor \frac{ai+b}{c} \right\rfloor}^2$, and $\sum\limits_{i=0}^{n} i \left\lfloor \frac{ai+b}{c} \right\rfloor$. Output each answer modulo $998244353$. There are multiple test cases.

Input Format

The first line contains the number of test cases $t$.

The next $t$ lines each contain four integers, which are $n,\ a,\ b,\ c$ for that test case.

Output Format

For each test case, output one line with three integers, which are the three answers modulo $998244353$.

2
2 1 0 2
4 3 9 6

1 1 2
11 27 27

Hint

This problem uses $\mathrm{Special}\ \mathrm{Judge}$.

If you answer all cases for the first query correctly, you can get $40\%$ of the total score. If you answer all cases for the second and third queries correctly, you can get an additional $30\%$ for each.

For all test points, $1 \leqslant t \leqslant 10^5,\ 0 \leqslant n,\,a,\,b,\,c \leqslant 10^9,\ c \neq 0$.

Translated by ChatGPT 5