Alice 有一个变换规则，如果他手里的数当前为 w, 那么下一秒变为 (x1 ∗ w + y1)\%m, Bob 有一个变换规则，如果他手里的数当前为 w, 那么下一秒变为 (x2 ∗ w + y2)\%m 第 0 秒的时候，Alice 手上的数为 h_1, Bob 手上的数为 h_2, 请问最快在第几秒恰好 Alice 手 上的数字是 a_1 且 Bob 手上的数字是 a_2 ，若永远不可能则输出 -1

第一行 T 表示数据组数 

每一组数据第一行为 m，第二行两个正整数 h_1, a_1, 第三行两个正整数 x_1, y_1, 第三行两个 正整数 h_2, a_2, 第三行两个正整数 x_2, y_2

共 T 行，如题目描述

对于 30% 的据有 m ≤ 1000。 

对于 100% 的据有 T ≤ 5, h_1 \neq a_1, h_2 \neq a_2, 2 ≤ m ≤ 1000000, 0 ≤ h_1, a_1, x_1, y_1, h_2, a_2, x_2, y_2 ≤ m