일차식의 나머지의 최솟값

각 테스트 케이스는 $T$개의 케이스로 구성된다.

$N, M, A, B$이 주어진다. $\min\lbrace (Ax+B)\bmod M\mid 0\leq x < N\rbrace$을 출력한다.

제약 조건

• $1 \leq T \leq 100000$
• $1 \leq N, M \leq 1000000000$
• $0 \leq 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}$

$N, M, A, B$이 주어진다. $\min\lbrace (Ax+B)\bmod M\mid 0\leq x < N\rbrace$을 출력한다.