现 有 两 个 人 , 若 第 一 个 人 当 前 手 中 的 数 为 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。

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

【数据规模】

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

对于 100%的数据,

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