A number is Almost-K-Prime if it has exactly K prime numbers (not necessarily distinct) in its prime factorization. For example, 12 = 2 * 2 * 3 is an Almost-3-Prime and 32 = 2 * 2 * 2 * 2 * 2 is an Almost-5-Prime number. A number X is called Almost-K-First-P-Prime if it satisfies the following criterions:

1. X is an Almost-K-Prime and
2. has all and only the first P (P ≤ K) primes in its prime factorization.

For example, if K = 3 and P = 2, the numbers 18 = 2 * 3 * 3 and 12 = 2 * 2 * 3 satisfy the above criterions. And 630 = 2 * 3 * 3 * 5 * 7 is an example of Almost-5-First-4-Pime.

For a given K and P, your task is to calculate the summation of $\phi(X)$ for all integers X such that X is an Almost-K-First-P-Prime.

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing two integers K (1 ≤ K ≤ 500) and P (1 ≤ P ≤ K).

For each case, print the case number and the result modulo 1000000007 (10⁹ + 7).

1. In mathematics $\phi(X)$ means the number of relatively prime numbers with respect to X which are smaller than X. Two numbers are relatively prime if their GCD (Greatest Common Divisor) is 1. For example, $\phi(12)$ = 4, because the numbers that are relatively prime to 12 are: 1, 5, 7, 11.2. For the first case, K = 3 and P = 2 we have only two such numbers which are Almost-3-First-2-Prime, 18=233 and 12=223. The result is therefore, $\phi(12) + \phi(18) = 10$.