Lostmonkey 费了好大劲才得到 fsk 公司基层流水线操作员的职位。流水线上有 $n$ 个位置，从 $0$ 到 $n-1$ 依次编号，一开始的初始状态为：$0$ 号位置为空位；对 $0 < i < n$，$i$ 号位置上有编号为 $i$ 的盒子。

Lostmonkey 要按以下规则重新排列这些盒子。

重新排列的规则由 $5$ 个数 $q,p,m,d,s$ 来描述，其中 $s$ 表示要求 $s$ 号位置最终为空位。为了确定所有盒子的最终位置，首先生成一个序列 $c$，$c_0=0$，$c_{i+1}=(c_i\cdot q+p)\bmod m$。然后从编号为 $1$ 的盒子开始按编号从小到大的顺序依次生成每个盒子的最终位置，直到给编号为 $n-1$ 的盒子生成最终位置。

假设编号为 $i$ 的盒子最终被放到 $pos_i$ 号位置，那么 $pos_i=(c_i+d\cdot x_i+y_i)\bmod n$， 其中 $x_i$ 和 $y_i$ 是为确保编号为 $i$ 的盒子不与编号小于 $i$ 的盒子放到相同位置而由你设定的非负整数，且 $pos_i$ 不能为 $s$。若有多个 $x_i$ 和 $y_i$ 满足要求，你必须选择最小的 $y_i$，在 $y_i$ 相同时必须选择最小的 $x_i$。

这样，根据以上规则你可以确定所有盒子的最终位置，也就是终止状态。

假设通过一次移动你可以把某个盒子移到空位上，移动后被移盒子原来所在位置变成空位。请问最少需要多少次移动才能把所有盒子从初始状态转换成终止状态？

输入格式

输入第一行是一个整数 $t$，表示数据组数（每组数据描述一个要重新排列的问题）。接下来从输入文件第二行开始有 $t$ 组数据，每组数据只有一行，是用空格隔开的六个整数 $n,s,q,p,m,d$，其含义如上所述。

输入的数据保证 $30%$ 的数据满足 $n\le 100$。$100%$ 的数据满足 $t\le 20,n\le 100000,s < n$。其余的所有数字均为不超过 $100000$ 的正整数。

输出格式

输出包含 $t$ 行，第 $i$ 行输出对输入中给出的第 $i$ 个重新排列问题，把所有盒子从初始状态转换成终止状态需要的最少移动次数。

样例数据

Input

1
8 3 5 2 7 4

Output

6

样例解释

在终止状态，编号为 $1$ 的盒子到编号为 $7$ 的盒子依次被放到 $2,5,6,4,1,0,7$ 号位置。计算过程中表示式的值可能超过整型范围。