One of your friends desperately needs your help. He is working with a secret agency and doing some encoding stuffs. As the mission is confidential he does not tell you much about that, he just want you to help him with a special property of a number. This property can be expressed as a function f (n) for a positive integer n. It is defined as:

f (n) = (p + q)

In other words, he needs the sum of all possible pairs whose least common multiple is n. (The least common multiple (LCM) of two numbers p and q is the lowest positive integer which can be perfectly divided by both p and q). For example, there are 5 different pairs having their LCM equal to 6 as (1, 6), (2, 6), (2, 3), (3, 6), (6, 6). So f (6) is calculated as f (6) = (1 + 6) + (2 + 6) + (2 + 3) + (3 + 6) + (6 + 6) = 7 + 8 + 5 + 9 + 12 = 41.

Your friend knows you are good at solving this kind of problems, so he asked you to lend a hand. He also does not want to disturb you much, so to assist you he has factorized the number. He thinks it may help you.

Input 

The first line of input will contain the number of test cases T (T500). After that there will be T test cases. Each of the test cases will start with a positive number C (C15) denoting the number of prime factors of n. Then there will be C lines each containing two numbers P_i and a_i denoting the prime factor and its power (P_i is a prime between 2 and 1000) and ( 1a_i50). All the primes for an input case will be distinct.

Output 

For each of the test cases produce one line of output denoting the case number and f (n) modulo 1000000007. See the output for sample input forexact formatting.

Sample Input 

3
2
2 1
3 1
2
2 2
3 1
1
5 1

Sample Output 

Case 1: 41
Case 2: 117
Case 3: 16

#include <stdio.h>
#define mod 1000000007LL
int main() {
    int testcase;
    int cases, n, i, j;
    long long pi, ai, ans;
    scanf("%d", &testcase);
    cases = 0;
    while(testcase--) {
        scanf("%d", &n);
        ans = 1;
        long long N = 1;
        for(i = 0; i < n; i++) {
            scanf("%lld %lld", &pi, &ai);
            long long tmp = 1, sum = 0;
            for(j = 0; j < ai; j++) {
                sum += tmp;
                sum %= mod;
                tmp = tmp*pi;
                tmp %= mod;
            }
            N *= tmp;
            N %= mod;
            tmp = tmp*(ai+1);
            tmp %= mod;
            sum = (sum+tmp)%mod;
            ans *= sum;
            ans %= mod;
        }
        printf("Case %d: %lld\n", ++cases, (ans+N)%mod);
    }
    return 0;
}