第一行一个整数 $T$ ，表示数据组数。

接下来有 $T$ 行，每行表示一组数据。

每组数据依次有 $m,\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{d},a,b,c,d$ 六个整数，其中 $m,a,b$ 的意义与题面中相同；
$d$ 表示是否只考虑第一种事件：$d$ 的取值为 $0$ 或 $1$ ，为特殊参数。当 $d=1$ 时，请忽视所有的第二种事件与第三种事件（忽视的含义见题面描述）。
$\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{d},c$ 是随机数生成器的参数。

我们使用如下实现的随机数生成器 $\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{n}\mathrm{u}\mathrm{m}()$。每组数据输入该组数据中 $\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{d}$ 的初始值。

unsigned 32bit integer seed

function randnum()
    seed = seed xor (seed lsh 13)
    seed = seed xor (seed rsh 17)
    seed = seed xor (seed lsh 5)
    return seed
end function

计算 $p[]$ 的代码如下：

for i = 1 to m by step 1
    if randnum() mod c == 0 then
        p[i] = -1
    else
        p[i] = randnum() mod b
    end if
end for

我们在「数据范围与提示」的最后提供了这道题的一个输入输出模板（也可以在附加文件中下载），如果你不需要，请忽视它。

每组数据输出一行表示答案。

样例输入

1
7 327711436 4 6 3 0

样例输出

292

样例解释

$p$ 序列为$[5,-1,2,-1,2,5,4]$ 。初始时卡车上已经有了编号为 $[0,4]$ 的红茶。

第一个时刻，发生第一种事件，编号为 $5$ 的红茶加入卡车，此时卡车上编号为 $[0,5]$ 的红茶都有，而编号为 $6$ 的红茶没有，因此 ans1=6ans_1=6ans​1​​=6 。

第二个时刻，理论上应该发生第三种事件，但是并没有红茶飞出了卡车，因此该事件被忽视， ans2=0ans_2=0ans​2​​=0 。

第三个时刻，发生第二种事件，编号为 $2$ 的红茶飞出卡车，此时卡车上编号为 $[0,1]$ 的红茶都有，而编号为 $2$ 的红茶没有，因此 ans3=2ans_3=2ans​3​​=2 。

第四个时刻，发生第三种事件，魔理沙捡回编号为 $2$ 的红茶回卡车，此时与第一个时刻后情况一致，因此 ans4=6ans_4=6ans​4​​=6 。

第五个时刻和第三个时刻一致，因此 ans5=2ans_5=2ans​5​​=2 。

第六个时刻，发生第二种事件，编号为 $5$ 的红茶飞出卡车，此时卡车上编号为 $0,1,3,4$ 的红茶都有，而编号为 $2,5$ 的红茶没有，因此 ans6=2ans_6=2ans​6​​=2 。

第七个时刻，发生第二种事件，编号为 $4$ 的红茶飞出卡车，此时卡车上编号为 $0,1,3$ 的红茶都有，而编号为 $2,4,5$ 的红茶没有，因此 ans7=2ans_7=2ans​7​​=2 。

更多样例

请在页面上方的附加文件中下载。

本题 C/C++ 时限 2.5 秒，Pascal 时限 5 秒。最后将改时限重测所有 Pascal 提交。

对于所有数据，1≤m≤1061 \leq m \leq 10^61≤m≤10​6​​，$1\le T\le 50$ ， $-1\le a\le m$ ， $1\le b\le 2\times m$ ， 1≤c≤1071 \leq c \leq 10^71≤c≤10​7​​ ， $0\le d\le 1$ 。

$d$ 表示是否只考虑第一种事件：$d$ 的取值为 $0$ 或 $1$ ，为特殊参数。当 $d=1$ 时，请忽视所有的第二种事件与第三种事件（忽视的含义见题面描述）。
注意，$d=1$ 时原本合法的事件也要被忽视，故即使你没有用到这个性质，也要记得判断 $d=1$ 的情况。除测试点 $7$ 以外的测试点也有可能出现 $d=1$ 的数据。