НОК пари сумм
Один із ваших друзів терміново потребує вашої допомоги. Він працює в секретному агентстві, займаючись питаннями кодування. Оскільки його місія є конфіденційною, він не може розповісти вам про неї. Він лише просить вас допомогти йому з особливою властивістю чисел. Ця властивість може бути виражена як функція 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 рядків містить два числа p[i] і a[i], що описують простий дільник і його степінь (p[i] - просте число між 2 і 1000, 1 ≤ a[i] ≤ 50). Усі прості числа в одному тесті різні.
Вихідні дані
Для кожного тесту виведіть в окремому рядку номер тесту і f(n) mod 1000000007 як наведено в прикладі.