线性函数下取整之和 (Sum of Floor of Linear)

时间限制：5 秒

题目描述

每个测试包含 $T$ 组数据。

给定 $N, M, A, B$。输出 $\sum_{i=0}^{N-1} \lfloor (A \times i + B) / M \rfloor$。

约束条件

• $1 \le T \le 100,000$
• $1 \le N, M \le 10^9$
• $0 \le A, B < M$

输入

T
N_0 M_0 A_0 B_0
N_1 M_1 A_1 B_1
⋮
N_{T-1} M_{T-1} A_{T-1} B_{T-1}

5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999

3
13
0
314095480
499999999500000000