Mr. Toluene is building an online judge and has noticed that participants in contests are very concerned about their rankings. In an ACM-style contest, if the number of solved problems is different, the person with more solved problems is ranked higher. If the number of solved problems is the same, the person with less penalty time is ranked higher. Mr. Toluene would like you to help design a program that, every time someone solves a problem, tells them how many people are ranked ahead of them (excluding those who have the same number of solved problems and the same penalty time).

Input

The first line contains an integer $T$ representing the number of test cases. For each test case: input three integers $m, n, \text{seed}$. $m$ represents the total number of participants (numbered $1$ to $m$), and $n$ represents the total number of accepts (assuming accepts are already deduplicated, i.e., there are no duplicate submissions for the same problem by the same person). $\text{seed}$ represents the seed for data generation.

You are required to use the following function to generate the data:

typedef unsigned int ui ;
ui randNum ( ui& seed , ui l a s t , const ui m){
seed = seed * 17 + last;
return seed % m + 1 ;
}

(where last is the result of the previous output; if no output has been produced yet, last = 7)

For each of the $n$ submissions, generate two values $Ria$ and $Rib$, indicating that participant $Ria$ has accepted a problem with a penalty time of $Rib$. (This means $Ria$'s number of solved problems increases by $1$, and their total penalty time increases by $Rib$).

It is guaranteed that a total of $n$ sets of data are generated, representing $n$ total submissions. For all data, it is guaranteed that the sum of penalty times does not exceed $1,500,000$.

Output

For each submission, output one integer on a new line, representing how many participants have a higher score than $Ria$ after the current accept.

Constraints

Examples

Input 1

1
7 3 1

Output 1

0
1
0