线性函数取整求和

【题目描述】

本题共包含 $T$ 组测试数据。

给定 $N, M, A, B$，求 $\sum_{i = 0}^{N - 1} floor((A \times i + 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}$

【输出】

对每组测试数据，输出一行一个整数，即 $\sum_{i = 0}^{N - 1} floor((A \times i + B) / M)$。

【输入样例】

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

【数据范围】

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

【来源】

Library Checker（yosupo06） sum_of_floor_of_linear