SP10465 OTOY1 - One Theorem, One Year

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 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. 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 starts with an integer **T (, denoting the number of test cases.** Each case starts with a line containing two integers **K (1 and **P (1 .****

For each case, print the case number and the result modulo **1000000007**.