Người ta muốn xây dựng một sân đáp trực thăng trên nóc một tòa nhà để trực thăng có thể hạ cánh.

Sân đáp trực thăng phải thỏa mãn tất cả các điều kiện sau:

• Sân đáp trực thăng bao gồm $k$ ($k \ge 1$) đường tròn đồng tâm.
• Bán kính của các đường tròn tạo nên sân đáp trực thăng lần lượt là $1, 2, \dots, k$ (các số tự nhiên phân biệt từ $1$ đến $k$).
• Chu vi của mỗi đường tròn phải được sơn bằng đúng một màu sơn duy nhất.

Kích thước của sân đáp trực thăng là bán kính của đường tròn lớn nhất trong số các đường tròn đồng tâm, và theo điều kiện trên, ta thấy nó bằng số lượng đường tròn đồng tâm $k$.

Hai sân đáp trực thăng được coi là khác nhau nếu kích thước của chúng khác nhau, hoặc kích thước bằng nhau nhưng tổ hợp màu sơn của các đường tròn đồng tâm khác nhau.

Để sơn chu vi của một đường tròn bán kính $r$, cần dùng chính xác $r$ thùng sơn.

Ví dụ, khi có 3 thùng sơn đỏ và 4 thùng sơn xanh, có 9 loại sân đáp trực thăng khác nhau có thể tạo thành bằng cách sử dụng lượng sơn này, như trong hình dưới đây. Dấu X biểu thị tâm của các đường tròn đồng tâm.

Lưu ý rằng, trong số các sân đáp kích thước 3, để vẽ như hình dưới đây cần $4=1+3$ thùng sơn đỏ và 2 thùng sơn xanh, nhưng vì lượng sơn đỏ được cho chỉ có 3 thùng nên không đủ, do đó không thể tạo ra sân đáp như vậy.

Hiện tại bạn có $a$ thùng sơn đỏ và $b$ thùng sơn xanh. Hãy viết chương trình tính số lượng sân đáp trực thăng khác nhau có thể tạo thành chỉ bằng lượng sơn này, chia lấy dư cho $10^9 + 7$.

Bạn cần giải quyết $T$ trường hợp thử nghiệm trong một lần chạy.

Giới hạn

• Tất cả các số được cho đều là số nguyên.
• $1 \le T \le 10\ 000$
• $1 \le a, b \le 50\ 000$

Subtask

1. (3 điểm) $T = 1$. $a, b \le 6$.
2. (17 điểm) $T = 1$. $a, b \le 100$.
3. (21 điểm) $T = 1$. $a, b \le 1\ 000$.
4. (23 điểm) $T = 1$. $a, b \le 5\ 000$.
5. (26 điểm) $T = 1$.
6. (10 điểm) Không có ràng buộc bổ sung nào.

Dữ liệu vào

Dòng đầu tiên chứa số lượng trường hợp thử nghiệm $T$.

$T$ dòng tiếp theo, mỗi dòng chứa một trường hợp thử nghiệm gồm hai số nguyên $a$ và $b$ cách nhau bởi một dấu cách.

Dữ liệu ra

Với mỗi trường hợp thử nghiệm, in ra trên một dòng số lượng sân đáp trực thăng khác nhau có thể tạo thành chỉ từ $a$ thùng sơn đỏ và $b$ thùng sơn xanh, chia lấy dư cho $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

3
3 4
10 5
7 12

Dữ liệu ra 1

9
25
40