Один из Ваших друзей экстренно нуждается в Вашей помощи. Он работает в секретном агентстве и занимается вопросами кодирования. Поскольку его миссия является конфиденциальной, он не рассказывает Вам о ней. Он просто хочет, чтобы Вы помогли ему с особым свойством чисел. Это свойство может быть выражено как функция f(n) для некоторого натурального n. Она определяется так:

Другими словами, требуется найти сумму всех возможных пар чисел, наименьшее общее кратное которых равно n. Наименьшим общим кратным (НОК) двух чисел p и q называется наименьшее натуральное число, которое нацело делится на p и q. Например, существует 5 различных пар чисел, НОК которых равен 6: (1, 6), (2, 6), (2, 3), (3, 6), (6, 6). Поэтому f(6) = (1 + 6) + (2 + 6) + (2 + 3) + (3 + 6) + (6 + 6) = 7 + 8 + 5 + 9 + 12 = 41.

Ваш друг знает, что Вы хорошо решаете задачи такого рода, поэтому он попросил Вас помочь. Он не хочет Вас особо беспокоить, поэтому в качестве помощи он разложил входное число на множители. Он считает, что это поможет Вам.

Входные данные

Первая строка содержит количество тестов t (t ≤ 500). Каждый тест начинается с натурального числа c (c ≤ 5) - количества простых делителей n. Каждая из следующих c строк содержит два числа pi и ai, описывающие простой делитель и его степень (pi - простое число между 2 и 1000, 1 ≤ ai ≤ 50). Все простые числа в одном тесте различны.

Выходные данные

Для каждого теста выведите в отдельной строке номер теста и f(n) mod 1000000007 как приведено в примере.