Gretchen and Strange Function

Gretchen loves experimenting with functions. She came up with an interesting function recently that looks like the following:

int H-function ( int N, int A, int B, int C ) {
	
    if ( B > N ) return A;
    
    int curA = A;
    
    while ( true ) {
        int newA = curA + C * B;
        if ( newA < 1 || newA > N ) break;
        curA = newA;
    }
    
    return H-function ( N, curA, B+1, (-1)*C );
    
}

She wonders what values H-function will return for different values of the parameters. Since you are the smartest friend she has, she asked you to help her solve this problem.

Given the values of N, A, and B, tell her the return value of H-function ( N, A, B, 1 ).

Input

The first line of input contains two integers: T, N. Here, T is the number of queries Gretchen will make.

Each of the next T lines contains two space-separated integers: A, B.

Constraints

1 <= T <= 3*105
1 <= N, A, B <= 104
A <= N
B <= N

Output

For each query, print the return value of H-function ( N, A, B, 1 ) on a new line.

Sample

Input	Output
2 3 1 1 1 2	1 3

####Explanation:

Let us look at the calls made to H-function in the first query:
H-function (3,1,1,1)
H-function (3,3,2,-1)
H-function (3,1,3,1)
H-function (3,1,4,-1) -> returns 1

Let us look at the calls made to H-function in the second query:
H-function (3,1,2,1)
H-function (3,3,3,-1)
H-function (3,3,4,1) -> returns 3