建物の屋上にヘリコプターが着陸できるように、ヘリポート（ヘリ着陸場）を作ろうとしている。
ヘリポートは以下の条件をすべて満たさなければならない。
- ヘリポートは $k$ ($k \ge 1$) 個の同心円で構成される。
- ヘリポートを構成する各円の半径は $1, 2, \dots, k$ ($1$ 以上 $k$ 以下の相異なる自然数) である。
- 各円の円周は、1色のペンキで塗られなければならない。
ヘリポートの大きさとは同心円のうち半径が最も大きい円の半径であり、上記の条件より同心円の個数 $k$ と等しいことがわかる。
2つのヘリポートが異なるとは、ヘリポートの大きさが異なるか、大きさは同じであっても同心円に塗られた色の組み合わせが異なることを意味する。
半径 $r$ の円周を塗るためには、ちょうど $r$ 缶のペンキが必要である。
例えば、赤のペンキが 3 缶、青のペンキが 4 缶あるとき、これらのペンキを用いて作ることができる相異なるヘリポートは、下の図に示すように 9 種類ある。X の印は同心円の中心を表している。
なお、大きさが 3 のヘリポートのうち、下の図に示すように描くには赤のペンキが $4 = 1 + 3$ 缶、青のペンキが 2 缶必要となるが、与えられた赤のペンキ 3 缶では不足するため、このようなヘリポートを作ることはできない。
現在、あなたには赤のペンキが $a$ 缶、青のペンキが $b$ 缶ある。これらのみを用いて作ることができる相異なるヘリポートの数を $10^9 + 7$ で割った余りを求めるプログラムを作成せよ。
1つの入力で $T$ 個のテストケースを解く必要がある。
制約
- 与えられる数はすべて整数である。
- $1 \le T \le 10\ 000$
- $1 \le a, b \le 50\ 000$
小課題
- (3点) $T = 1$, $a, b \le 6$。
- (17点) $T = 1$, $a, b \le 100$。
- (21点) $T = 1$, $a, b \le 1\ 000$。
- (23点) $T = 1$, $a, b \le 5\ 000$。
- (26点) $T = 1$。
- (10点) 追加の制約はない。
入力
1行目にテストケースの数 $T$ が与えられる。
続く $T$ 行には、テストケースが1行に1つずつ与えられる。各行には2つの整数 $a$ と $b$ が空白を挟んで与えられる。
出力
各テストケースについて、赤のペンキ $a$ 缶と青のペンキ $b$ 缶のみを用いて作ることができる相異なるヘリポートの数を $10^9 + 7$ で割った余りを1行に1つずつ出力せよ。
入出力例
入力 1
3 3 4 10 5 7 12
出力 1
9 25 40