Changyoung's Password

Changyoung uses a function f to create passwords.

For a positive integer n, f(n) is defined as follows: find every unordered pair (a, b) with a ≤ b whose least common multiple is exactly n, and add up a + b over all such pairs.

For example, the pairs whose least common multiple is 6 are (1, 6), (2, 6), (2, 3), (3, 6), and (6, 6) — five in total — so

f(6) = (1+6) + (2+6) + (2+3) + (3+6) + (6+6) = 7 + 8 + 5 + 9 + 12 = 41.

Given the number n used to create a password, write a program that computes the password f(n). Because n can be extremely large, it is given by its prime factorization.

The first line contains the number of test cases T (T ≤ 500).

The first line of each test case contains C, the number of distinct prime factors of n (C ≤ 15).

Each of the next C lines contains a prime factor Pi and its exponent ai (2 ≤ Pi ≤ 1000, Pi is prime, 1 ≤ ai ≤ 50); that is, n = P1^a1 × P2^a2 × ⋯ × PC^aC. All primes given within a single test case are distinct.

For each test case, print f(n) modulo 1,000,000,007 on its own line.