Summations of Floor Function Series

Given four integers n, a, b, c, compute the following three summations modulo \(998244353\):

\(S_1 = \sum_{i=0}^{n}\left\lfloor \frac{a\,i+b}{c} \right\rfloor\)

\(S_2 = \sum_{i=0}^{n}\left(\left\lfloor \frac{a\,i+b}{c} \right\rfloor\right)^2\)

\(S_3 = \sum_{i=0}^{n} i\,\left\lfloor \frac{a\,i+b}{c} \right\rfloor\)

Here, \(\lfloor x \rfloor\) denotes the floor of \(x\). The input consists of multiple test cases.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each of the following \(T\) lines contains four integers \(n\), \(a\), \(b\), and \(c\), separated by spaces.

outputFormat

For each test case, output three space-separated integers: \(S_1\), \(S_2\), and \(S_3\), each taken modulo \(998244353\).

sample

1
5 1 2 3

7 11 24