题目描述

有些代数式张得很像一张图，比如说 D*X % M。. 这些图就是传说中的数形图，有时候我们要求最小值就变成了最小数形图问题。 现在请求出满足 $L\leq D*X\%M\leq R$ 的 $X$ 的最小非负值，即这个数形图的最小权值。

输入格式

第一行一个整数 $task \leq 100000$ 表示数据组数。接下来 $task$ 行每行四个非负整数分别为 $M$（正数），$D$，$L$，$R$，保证都是 long long 范围内的数，不保证数据合法。

输出格式

$task$ 行，每行一个数表示所求的最小 $X$。 如果无解请输出$-1$。

输入样例

2
3 4 2 1
5 2 3 4

输出样例

-1
2