问题描述

有一个序列 $X=(X_0, X_1, \\ldots)$，由以下递推关系定义。

$X_i = \\left\\{ \\begin{array}{ll} S & (i = 0)\\\\ (A X_{i-1}+B) \\bmod P & (i \\geq 1) \\end{array} \\right.$

确定是否存在一个 $i$，使得 $X_i=G$。如果存在，找到最小的 $i$。
这里，$x \\bmod y$ 表示 $x$ 被 $y$ 整除的余数（最小的非负余数）。

对于每个输入文件，给出了 $T$ 个测试用例。

约束条件

• $1 \\leq T \\leq 100$
• $2 \\leq P \\leq 10^9$
• $P$ 是素数。
• $0\\leq A,B,S,G < P$
• 输入的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$T$ $\\mathrm{case}_1$ $\\mathrm{case}_2$ $\\vdots$ $\\mathrm{case}_T$

每个测试用例的格式如下：

$P$ $A$ $B$ $S$ $G$

输出

输出 $T$ 行。
第 $t$ 行应包含对于 $\\mathrm{case}_t$，使得 $X_i=G$ 的最小 $i$，或者 -1 如果不存在这样的 $i$。

样例输入 1

3
5 2 1 1 0
5 2 2 3 0
11 1 1 0 10

样例输出 1

3
-1
10

对于第一个测试用例，我们有 $X=(1,3,2,0,\\ldots)$，所以 $X_i=0$ 的最小 $i$ 是 $3$。
对于第二个测试用例，我们有 $X=(3,3,3,3,\\ldots)$，所以不存在 $i$ 使得 $X_i=0$。