Problem Description

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$

Output

For each case, output the answer.

2
4 7 1 13
11 4 2 12

6
1