[Hnoi2010]Fsk物品调度

现在找工作不容易，Lostmonkey 费了好大劲才得到 fsk 公司基层流水线操作员的职位。

流水线上有 $n$ 个位置，从 $0$ 到 $n-1$ 依次编号。一开始 $0$ 号位置为空，其他位置 $i$ 上有编号为 $i$ 的盒子。Lostmonkey 要按照以下规则重新排列这些盒子。

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

首先生成一个序列 $c$ ：

c_0=0,\qquad 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_i, y_i$ 满足要求，你需要选择 $y_i$ 最小的；当 $y_i$ 相同时选择 $x_i$ 最小的。

这样你就得到了所有盒子的最终位置。现在你每次可以把某个盒子移动到空位上，移动后原盒子所在的位置成为空位。请问把所有的盒子移动到目的位置所需的最少步数是多少。

输入格式

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

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

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

1
8 3 5 2 7 4

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

本题为 HNOI 2010 试题「Fsk 物品调度」，题面与测试数据整理自 BZOJ 1998。

1
8 3 5 2 7 4