题目描述

求 $3≤(3*x) Mod 5≤4$ 的最小正整数解是多少？3！这个很简单，但当把数字放得很大呢?

输入格式

第一行一个整数。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

题目来源

没有写明来源。