Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Gretchen and Strange Function

By Labib666 · Limits 1s, 512 MB

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

InputOutput
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

    Discussion

    Statistics


    57% Solution Ratio

    Submit

    Login to submit

    Related Contests

    The Tough Summer Spar 2016 Ended at 2016-08-01 12:00:00 +0000 UTC