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

$\binom{n}{m}$ represents the number of ways to choose $m$ balls from $n$ distinct balls, which is defined as:

$$ \binom{n}{m} = \frac{n!}{m!(n-m)!} $$

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

Input

Read the data from standard input.

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

The next $q$ lines each contain two integers $n$ and $m$, where $0 \le m \le n$ is guaranteed.

Output

Output to standard output.

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

Examples

Input 1

3
0 0
4 2
10 3

Output 1

1
4
16

Note

$\binom 0 0 = 1$, which has $1$ divisor.

$\binom 4 2 = 6$, which has $4$ divisors: $\{1, 2, 3, 6\}$.

$\binom {10} 3 = 120$, which has $16$ divisors: $\{1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120\}$.

Examples 2

See ex_divisor2.in and ex_divisor2.ans in the download directory.

Subtasks

For $100\%$ of the data, it is guaranteed that $q \le 10^{5}$ and $n \le 10^{5}$.

Special Property A: It is guaranteed that $\binom n m \le 10^6$.

Special Property B: It is guaranteed that the input $n$ is always the same value.