法珞是个可爱的山村姑娘，在做家务之余喜欢摆弄数字们，梦想是当一名小学数学老师。 一天她在书房收拾她的数字们时，不小心碰到了一个变量$x$。 $x$的初值为$x_0$，每碰一次$x$会变成$(kx+b)\ mod\ p$。 法珞希望把它恢复原样，请帮帮她吧。 求出最少碰多少次可以将$x$从$x_0$再变到$x_0$，若无法恢复原样输出-1。
输入的第一行，一个整数$T$表示数据组数。
接下来的$T$行，每一行四个非负整数$k, b, x_0, p$。
$1\leq T\leq 100$
$0\leq k,b, x_0 < p$
$1\leq p\leq 10^9+9$
一共$T$行，代表每组数据的答案。
2 4 7 1 13 11 4 2 12
6 1