OTOY1 - One Theorem, One Year

no tags 

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

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.

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.

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.

Example

Input:
3
3 2
5 4
99 45

Output:
Case 1: 10
Case 2: 816
Case 3: 49939643

hide comments
vaibhav2303: 2018-07-18 14:39:01

Same codee gave AC after TLE!

Last edit: 2018-07-18 15:38:32
Piyush Raman Srivastava: 2014-01-26 14:05:57

every time i encounter a question on etf, i learn something new about it! :)


Added by:Samir Ahmed
Date:2012-01-21
Time limit:1s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem