# 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

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*10 ^{5}**

**1 <= N, A, B <= 10**

^{4}**A <= N**

**B <= N**

### Output

For each query, print the ** return value** of

**H-function ( N, A, B, 1 )**on a new line.

### Samples

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**

#### Labib666

Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms. →

Login to submit