# LCM Pair Sum

Time Limit: 6 Seconds Memory Limit: 32768 KB

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) = SUM (p+q) where {1≤p≤q≤n, lcm(p,q)=n}

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 (T ≤ 500). After that there will be T test cases. Each of the test cases will start with a positive number C (C ≤ 15) denoting the number of prime factors of n. Then there will be C lines each containing two numbers Piand aidenoting the prime factor and its power (Pi is a prime between 2 and 1000) and (1 ≤ ai ≤ 50). 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 for exact 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: 16Submit

Source: SWERC 2012