99094 - 两个数

现 有 两 个 人 , 若 第 一 个 人 当 前 手 中 的 数 为 w1 , 则 下 一 秒 他 手 上 的 数 将 会 变 成 (x_1 *w_1 + y_1)mod m ; 若 第 二 个 人 当 前 手 中 的 数 为 w2, 则 下 一 秒 他 手 上 的 数 将 会 变 为 (x_2 *w_2 + y_2 )mod m (a mod b 表示 a 除以 b 的余数)。第 0 秒,两个人手上的数分别为 h1, h2; 请 求出最快在第几秒,第一个人手上的数为 a1,且第二个人手上的数为 a2。若不可能,则输出-1.

输入

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

对于接下来的每一组数据,第一行为一个正整数 m,第二行包括两个整数 h1, a1,第三行包括 两个整数 x1, y1,第四行包括两个整数 h2, a2,第五行包括两个整数 x2, y2。

输出

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

样例

输入

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

输出

3
-1

提示

【数据规模】

对于 30%的数据, m<=1000

对于 100%的数据,

T<=5, h1 不等于 a1 且 h2 不等于 a2,2<=m<=106 ,0<=h1,a2,x1,y1,h2,a2,x2,y2<m

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题