题目描述
现有两个人，若第一个人当前手中的数为 $w_1$，则下一秒他手上的数将会变成$(x_1 \times w_1+y_1) mod$ $m$。

若第二个人当前手中的数为 $w_2$ ，则下一秒他手上的数将会变为$(x_2 \times w_2+y_2) mod$ $m$ $(a$ $mod$ $b$ 表示 $a$ 除以 $b$ 的余数)。

第 0 秒，两个人手上的数分别为 $h_1$，$h_2$；请求出最快在第几秒，第一个人手上的数为 $a_1$,且第二个人手上的数为 $a_2$。

若不可能，则输出 $-1$。

输入格式

第一行为一个正整数 $T$，表示数据组数。

对于接下来的每一组数据：

• 第一行为一个正整数 $m$

• 第二行包括两个整数 $h_1$，$a_1$

• 第三行包括两个整数 $x_1$，$y_1$

• 第四行包括两个整数 $h_2$，$a_2$

• 第五行包括两个整数 $x_2$，$y_2$。

数据规模

• 对于 30% 的数据，$m \le 1000$

• 对于 100% 的数据，$T \le 5$，$h_1$ 不等于 $a_1$ 且 $h_2$ 不等于 $a_2$，$2 \le m \le 10^6$, $0 \le h_1,a_2,x_1,y_1,h_2,a_2,x_2,y_2 \lt m$

输出格式

对于每一组数据，输出一行，一个整数，如题所述。

输出格式

样例

2
5
4 2
1 1
0 1
2 3
1023
1 2
1 0
1 2
1 1

3
-1