暂无测试数据。

现在找工作不容易，Lostmonkey 费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有 $n$ 个位置，从 $0$ 到 $n-1$ 依次编号，一开始 $0$ 号位置空，其它的位置 $i$ 上有编号为 $i$ 的盒子。Lostmonkey 要按照以下规则重新排列这些盒子。 规则由 $5$ 个数描述，$q$，$p$，$m$，$d$，$s$，$s$ 表示空位的最终位置。首先生成一个序列 $c$，$c_0=0$，$c_i+1=(c_i*q+p) \mod m$。接下来从第一个盒子开始依次生成每个盒子的最终位置 $pos_i$，$pos_i=(c_i+d*x_i+y_i) \mod 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$ 意义如上所述。

对于 $30\%$ 的数据 $n \le 100$。

对于 $100\%$ 的数据 $t \le 20,n \le 100000,s<n$。其余所有数字均为不超过 $100000$ 的正整数。

输出格式

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

1
8 3 5 2 7 4

6