Pku3530A Modular Arithmetic Challenge

给定 $M, D, L, R$，求满足

$$L\le (D\times x)\bmod M\le R$$

的最小正整数解 $x$。

例如，求 $3\le (3x)\bmod 5\le 4$ 的最小正整数解。

输入格式

第一行一个整数 $T$，代表数据组数。

接下来 $T$ 行，每行 $4$ 个数 $M, D, L, R$，表示要求解 $L\le (D\times x)\bmod M\le R$。

输出格式

共 $T$ 行，表示 $x$ 的最小正整数解，若无解则输出 $-1$。

样例输入

1
5 3 3 4

样例输出

1

样例解释

取 $x=1$ 时 $(3\times 1)\bmod 5=3$，落在区间 $[3,4]$ 内，故最小正整数解为 $1$。

数据范围

• $T\le 100$；
• $1\le M, D, L, R\le 10^9$。

来源与许可

本题题面与测试数据整理自 BZOJ 1320。

样例 1

输入

1
5 3 3 4

输出

1