Kattis

# LCM Pair Sum

One of your friends desperately needs your help. He is working with a secret agency and doing some encoding stuff. As the mission is confidential he does not tell you much about that, he just wants 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 _{\substack {1\leq p\leq q\leq n\\ \mathrm{lcm}(p,q)=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$ ($T \leq 10$). After that there will be $T$ test cases.

Each of the test cases will start with a positive number $C$ ($C \leq 15$) 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 $1\, 000$) and ($1 \leq a_ i \leq 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 $1\, 000\, 000\, 007$. See the output for sample input for exact formatting.

Sample Input 1 Sample Output 1
3
2
2 1
3 1
2
2 2
3 1
1
5 1

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