問題文

$q$ 個のクエリが与えられます。各クエリについて、二項係数 $\binom{n}{m}$ の約数の個数を計算してください。

答えは非常に大きくなる可能性があるため、結果を $p = 10^9 + 7$ で割った余りを出力してください。

入力

1行目にクエリの数 $q$ が与えられます。

続く $q$ 行には、それぞれ2つの整数 $n, m$ が与えられます。ただし、$0 \le m \le n$ を満たすことが保証されます。

出力

$q$ 行にわたって、各クエリに対する答えを出力してください。

サンプル

入力 1

4
0 0
1 0
2 1
3 2

出力 1

1
1
2
2

入力 2

5
3 2
5 3
5 4
6 2
8 3

出力 2

2
4
2
4
8

サブタスク

• $10\%$ のデータについて、$q \le 10^{3}, n \le 10^{3}$ を満たす。
• $50\%$ のデータについて、$q \le 10^{5}, n \le 10^{5}$ を満たす。
• $100\%$ のデータについて、$q \le 5\times 10^{5}, n \le 10^{6}$ を満たす。