1421 - A Modular Arithmetic Challenge

求3<=(3*x) Mod 5<=4的最小正整数解是多少?3!这个很简单. 但当把数字放得很大呢?

输入

第一行一个整数。T代表数据组数。 接下来T行,每行4个数,M,D,L,R表示L<=(D*x Mod M)<=R。 T<=100,1<=M、D、L、R<=1000000000

输出

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

样例

输入

1
5 3 3 4

输出

1
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题