Alice 有一个变换规则：如果他手里的数当前为 w，那么下一秒变为 (x_1 * w + y_1) \bmod m。

Bob 有一个变换规则：如果他手里的数当前为 w，那么下一秒变为 (x_2 * w + y_2) \bmod m。

第 0 秒的时候，Alice 手上的数为 h_1，Bob 手上的数为 h_2。

请问最快在第几秒**恰好** Alice 手上的数字是 a_1 且 Bob 手上的数字是 a_2；若永远不可能则输出 `-1`。

- 第一行一个整数 m；

- 第二行两个整数 h_1, a_1；

- 第三行两个整数 x_1, y_1；

- 第四行两个整数 h_2, a_2；

- 第五行两个整数 x_2, y_2。

共 T 行，每行为该组数据的答案，若不可能输出 `-1`。

| 30% | m \le 1000 |

| 100% | T \le 5，h_1 \ne a_1，h_2 \ne a_2，2 \le m \le 10^6，0 \le h_1,a_1,x_1,y_1,h_2,a_2,x_2,y_2 \le m |