Migrated from Lutece 3163 关于抽象

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

注：本题不计一血。

在现代互联网中，当我们提到"抽象"的时候，脑子里面出现的可能是孙笑川、鼠鼠、emoji 等各种奇怪东西。似乎“抽象”这个词已经变成了不好懂、怪东西的代名词，而旁边的“抽象代数”则无辜躺枪。

hgg 觉得这不好，得科普一下。

“抽象”的本意是抽出大象，即从事物当中抽出其最本质的特征，而忽略其它在当前语境下不是很重要的细节。比方说当我们说到“1+1=2”时，其实并不是在讨论一个苹果加一个苹果等于两个苹果，又或者两个香蕉、两个海豚什么的。我们是从这一关系中抽象出了数量的概念，并在数量上做着新的研究。

群论认为正方体和 $S_4$ 是一样的。

拓扑学认为咖啡杯和甜甜圈是一样的。

范畴论认为群论和拓扑学中认为“某两个东西是一样的”是一样的。

把它们的某种相同的特点拿出来，然后一同研究。

---

这是一道类欧几里得算法的模板题，但是出题人希望你们可以去实现一下更通用（抽象）的万能欧几里得。

给定 $t$ 组数据，每组数据包含 $n,a,b,c$，试求出：

$$\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor,\sum_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor,\sum_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2 $$

答案对 $998244353$ 取模。

Input

第一行输入一个整数 $t$。 接下来 $t$ 行，每行输入一组 $n,a,b,c$。

Output

对于每组数据，以空格分隔输出一行数据。表示三个求和式的结果。 答案对 $998244353$ 取模。

Samples

2
2 1 1 2
4 3 9 6

2 3 2
11 27 27

Constraints

$1\leq t \leq 10^5$ $1\leq n,a,b,c \leq 10^6$

Resources

2024 UESTC ICPC Training for Math