题目描述

现在找工作不容易，Lostmonkey 费了好大劲才得到 fsk 公司基层流水线操作员的职位。流水线上有 $n$ 个位置，从 $0$ 到 $n - 1$ 依次编号，一开始 $0$ 号位置是空的，其它的位置 $i$ 上有编号为 $i$ 的盒子。Lostmonkey 要按照以下规则重新排列这些盒子。

规则由五个数描述，$q, p, m, d, s$，$s$ 表示空位的最终位置。

首先生成一个序列 $c$，$c_0=0$，$c_{i+1}=(c_i\times q+p)\bmod m$。

接下来从第一个盒子开始依次生成每个盒子的最终位置 $pos_i$，$pos_i=(c_i+d\times x_i+y_i)\bmod n$，$x_i,y_i$ 是为了让第 $i$ 个盒子不与之前的盒子位置相同的由你设定的非负整数，且 $pos_i$ 还不能为 $s$。

如果有多个序列 $x,y$ 满足要求，你需要选择 $y$ 的字典序最小的，当 $y$ 相同时选择 $x$ 字典序最小的。这样你得到了所有盒子的最终位置，现在你每次可以把某个盒子移动到空位上，移动后原盒子所在的位置成为空位。

问把所有的盒子移动到最终位置所需的最少步数。

输入格式

第一行包含一个整数 $t$，表示数据组数。

接下来 $t$ 行，每行六个数，$n, s, q, p, m, d$ 意义如上所述。

输出格式

对于每组数据输出一个数占一行，表示最少移动步数。

1
8 3 5 2 7 4

6

提示

【样例解释】

第 $1$ 个到第 $7$ 个盒子的最终位置依次是：$[2, 5, 6, 4, 1, 0, 7]$。

【数据范围】

对于 $30 \%$ 的数据，$n \le 100$，
对于 $100 \%$ 的数据，$1 \le t \le 20$，$1 \le n \le 100000$，$0 \le s < n$。

其余所有数字均为不超过 $100000$ 的正整数。

【提示】

计算过程可能超过整型范围。