Problem Description

Clarke is a patient with multiple personality disorder. One day, Clarke split into $n$ guys, named $1$ to $n$.
They will play a game called Lose Weight. Each of Clarkes has a weight $a[i]$. They have a baton which is always in the hand of who has the largest weight(if there are more than 2 guys have the same weight, choose the one who has the smaller order). The one who holds the baton needs to lose weight. i.e. $a[i]$ decreased by 1, where $i$ is the guy who holds the baton.
Now, Clarkes know the baton will be passed $q$ times. They want to know each one's weight after finishing this game.

Input

The first line contains an integer $T(1 \le T \le 10)$, the number of the test cases.
Each test case contains three integers $n, q, seed(1 \le n, q \le 10000000, \sum n \le 20000000, 1 \le seed \le 10^9+6)$, $seed$ denotes the random seed.
$a[i]$ generated by the following code.

  long long seed;
  int rand(int l, int r) {
    static long long mo=1e9+7, g=78125;
    return l+((seed*=g)%=mo)%(r-l+1);
  }

  int sum=rand(q, 10000000);
  for(int i=1; i<=n; i++) {
    a[i]=rand(0, sum/(n-i+1));
    sum-=a[i];
  }
  a[rand(1, n)]+=sum;

Output

Each test case print a line with a number which is $(b[1]+1) xor (b[2]+2) xor ... xor (b[n]+n)$, where $b[i]$ is the $ith$ Clarke's weight after finishing the game.

1
3 2 1

20303

Hint:
At first, $a[1]=20701, a[2]=31075, a[3]=26351$.  
At the first time, $a[2]$ decrease by 1.  
At the second time, $a[2]$ decrease by 1.  
Finally, $a[1]=20701, a[2]=31073, a[3]=26351$. So answer is $(20701+1)xor(31073+2)xor(26351+3)=20303$.