e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Summer School 2011 in Sevastopol, Day 7

Задача про делители

Для натурального x обозначим через f(x) наименьшее натуральное число n такое, что n·x имеет ровно x делителей не меньших n. Вам даны натуральные числа L и R, причём LR. Необходимо найти сумму

prb2489

где p = 109+7.

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

В первой строке входного файла задано натуральное число T105, количество тестов. В каждой из последующих T строк заданы через пробел целые числа L и R, причём 1LR107.

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

Для каждой пары чисел L и R из входного файла выведите в отдельной строке значения соответствующей суммы.

Time limit 5 seconds
Memory limit 64 MiB
Input example #1
3
1 2
3 6
1 10
Output example #1
2
27
726