Server Time: Mon Oct 26, 2020 7:15 am
Welcome ( logout
D - One Theorem, One Year
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

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.      X 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.

Sample Input

Output for Sample Input

3

3 2

5 4

99 45

Case 1: 10

Case 2: 816

Case 3: 49939643

Note

1.      In mathematics Φ(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, Φ(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=2*3*3 and 12=2*2*3. The result is therefore, Φ(12) + Φ(18) = 10.


Problem Setter: Samir Ahmed
Special Thanks: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan