当前没有测试数据。

G - 模P序列

得分：600分

问题描述

有一个按照以下递推关系定义的序列 $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$ 中最小的 $i$ 使得 $X_i=G$，如果不存在这样的 $i$ 则输出 -1。

---

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

3
-1
10

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