线性函数取模的最小值 (Min of Mod of Linear)

时间限制：10 秒

题目描述 (Problem Statement)

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

给定 $N, M, A, B$。请输出 $\min\{(Ax + B) \bmod M \mid 0 \le x < N\}$。

约束条件 (Constraints)

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

输入 (Input)

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

14
1 13 10 11
2 13 10 11
3 13 10 11
4 13 10 11
5 13 10 11
6 13 10 11
7 13 10 11
8 13 10 11
9 13 10 11
10 13 10 11
100 13 10 11
31415 92653 58979 32384
31415 9265358 9793 2384
1000000000 1000000000 999999999 999999999

11
8
5
2
2
2
2
2
0
0
0
1
24
0