最小数形图

时间限制:10s      空间限制:3MB

题目描述

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


输入格式

第一行一个整数 task<=100000 表示数据组数。 
接下来 task 行每行四个非负整数分别为 M(正数),D,L,R,保证都是 long long 范围内
的数,不保证数据合法。 


输出格式

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


样例输入

2 
3 4 2 1 
5 2 3 4 

样例输出

-1 
2 

提示

没有写明提示


题目来源

没有写明来源