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:
- X is an Almost-K-Prime and
- 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 ϕ(X) for all integers X such that X is an Almost-K-First-P-Prime.
Input
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).
Output
For each case, print the case number and the result modulo 1000000007 (109 + 7).
Sample
| Sample Input | Sample Output |
|---|---|
3 3 2 5 4 99 45 | Case 1: 10 Case 2: 816 Case 3: 49939643 |
Notes
- 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$.
