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

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

где p = 10^9+7.

Input

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

Output

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

Examples