Pku3530A Modular Arithmetic Challenge

时间限制:1s    【提交】    空间限制:64MB

题目描述

求3<=(3*x) Mod 5<=4的最小正整数解


输入格式

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


输出格式

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


样例输入

1
5 3 3 4

样例输出

1



提示

T<=100 1<=M、D、L、R<=1000000000


题目来源

没有写明来源