题目描述

求 $L\leq (D\times x) \bmod M\leq R$ 的最小正整数解

输入格式

第一行一个整数。T代表数据组数。 接下来T行，每行4个数，M，D，L，R表示$L\leq (D\times x) \bmod M\leq R$。

输出格式

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

1
5 3 3 4

1

提示

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