Falsyta is a lovely village girl. She loves to play with numbers besides doing housework. Her dream is to be a math teacher in a primary school.
One day when she was putting her numbers in order, she touched a variable $x$ accidentally.
The initial value of $x$ was $x_0$. Once $x$ was touched its value would become $(kx+b)\ mod\ P$ĄŁ
Falsyta wanted to restore it, so please help herĄŁ
Please find out the minimum touches to turn $x$ back to $x_0$ from $x_0$. If itĄŻs impossible, please print -1.
Input
The first line is an integer $T$, representing the number of casesĄŁ
The following $T$ lines, four non-negative numbers each line, $k, b, x_0, P$ respectively.
$1\leq T\leq 100$
$0\leq k,b, x_0 < p$
$1\leq p\leq 10^9+9$
