给定质数 $P$。 有 $n$ 组询问给定 $A,B,C,D$， 求最小的 $Ax+By$ 使得 $x,y$ 均为整数且 $C^x\equiv D^y\pmod P$。

7 3
1 2 3 4
4 3 2 1
5 2 8 2

6
15
11

$1\leq n\leq 6000，1\leq P,A,B,C,D\leq 10^9$。

game