You are given $q$ queries. For each query, you need to calculate the number of divisors of the binomial coefficient $\binom{n}{m}$.

Since the answer can be very large, you only need to output the result modulo $p = 10^9 + 7$.

Input

The first line contains a positive integer $q$, representing the number of queries.

Each of the next $q$ lines contains two integers $n$ and $m$, where $0 \le m \le n$.

Output

Output $q$ lines, each containing an integer representing the answer to the corresponding query.

Subtasks

For $10\%$ of the data, $q \le 10^{3}$ and $n \le 10^{3}$.

For $50\%$ of the data, $q \le 10^{5}$ and $n \le 10^{5}$.

For $100\%$ of the data, $q \le 5\times 10^{5}$ and $n \le 10^{6}$.

Examples

Input 1

4
0 0
1 0
2 1
3 2

Output 1

1
1
2
2

Input 2

5
3 2
5 3
5 4
6 2
8 3

Output 2

2
4
2
4
8