$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.
