You want to build a helipad on the roof of a building so that a helicopter can land on it.

A helipad must satisfy all of the following conditions:

• The helipad consists of $k$ ($k \ge 1$) concentric circles.
• The radii of the circles that make up the helipad are $1, 2, \dots, k$ (distinct positive integers from $1$ to $k$).
• The circumference of each circle must be painted with a single color of paint.

The size of a helipad is the radius of the largest circle among the concentric circles, which, from the conditions above, can be seen to be equal to the number of concentric circles $k$.

Two helipads are considered different if their sizes are different, or if their sizes are the same but the combination of colors painted on the concentric circles is different.

To paint the circumference of a circle of radius $r$, exactly $r$ cans of paint are required.

For example, when you have 3 cans of red paint and 4 cans of blue paint, there are 9 different helipads that can be made using these paints, as shown in the figure below. The X marks the center of the concentric circles.

For reference, to paint a helipad of size 3 as shown in the figure below, $4=1+3$ cans of red paint and 2 cans of blue paint would be needed. Since the given 3 cans of red paint are not enough, such a helipad cannot be made.

Currently, you have $a$ cans of red paint and $b$ cans of blue paint. Write a program to find the number of different helipads that can be made using only these paints, modulo $10^9 + 7$.

You need to solve $T$ test cases in a single input.

Constraints

• All given numbers are integers.
• $1 \le T \le 10\ 000$
• $1 \le a, b \le 50\ 000$

Subtasks

1. (3 points) $T = 1$. $a, b \le 6$.
2. (17 points) $T = 1$. $a, b \le 100$.
3. (21 points) $T = 1$. $a, b \le 1\ 000$.
4. (23 points) $T = 1$. $a, b \le 5\ 000$.
5. (26 points) $T = 1$.
6. (10 points) No additional constraints.

Input

The first line contains the number of test cases $T$.

The next $T$ lines describe the test cases, one per line. Each line contains two integers $a$ and $b$, separated by a space.

Output

For each test case, output on a single line the number of different helipads that can be made using only $a$ cans of red paint and $b$ cans of blue paint, modulo $10^9 + 7$.

Examples

Input 1

3
3 4
10 5
7 12

Output 1

9
25
40