Problem Description

$ZYB$ has a tree with $N$ nodes,now he wants you to solve the numbers of nodes distanced no more than $K$ for each node.
the distance between two nodes$(x,y)$ is defined the number of edges on their shortest path in the tree.

To save the time of reading and printing,we use the following way:

For reading:we have two numbers $A$ and $B$,let $fa_i$ be the father of node $i$,$fa_1=0$,$fa_i=(A*i+B)\%(i-1)+1$ for $ i \in [2,N]$ .

For printing:let $ans_i$ be the answer of node $i$,you only need to print the $xor$ $sum$ of all $ans_i$.

Input

In the first line there is the number of testcases $T$.

For each teatcase:

In the first line there are four numbers $N$,$K$,$A$,$B$

$1 \leq T \leq 5$,$1 \leq N \leq 500000$,$1 \leq K \leq 10$,$1 \leq A,B \leq 1000000$

Output

For $T$ lines,each line print the ans.

Please open the stack by yourself.

$N \geq 100000$ are only for two tests finally.

1
3 1 1 1

3