模 $P$ 下的序列

题目描述

有一个由以下递推式定义的序列 $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$ 个测试用例。

输入格式

输入按以下格式从标准输入给出:

$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$,若不存在这样的 $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)$,所以不存在满足 $X_i=0$ 的 $i$。

数据范围

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