Nugget has failed his most recent math test on multiplication. To help him improve, Bruce has given Nugget queries about multiplication. Each query comes in the form: `x y`

, where and are non-negative integers. To solve the query, you must print out the product of all the integers between and (inclusive) modulo . Being a very ~~lazy~~ busy boy, Nugget asks you to build a program that can do this for him. As a reward, he offers you 7 points.

**Note: If you are using Python 2/3, you should submit using PyPy 2/3 with fast I/O.**

#### Input Specification

The first line will contain a positive integer representing the number of queries.

The next lines will contain non-negative integers and separated by a space.

#### Output Specification

On the line, output the product of the integers between and modulo of the query.

#### Constraints

For all subtasks:

##### Subtask 1 [15%]

##### Subtask 2 [85%]

No additional constraints.

#### Sample Input 1

```
4
1 4
2 4
3 4
4 4
```

#### Sample Output 1

```
24
24
12
4
```

#### Sample Input 2

```
3
10 999
17 1910
500000 505000
```

#### Sample Output 2

```
66208545
58404876
841914375
```

## Comments