Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Jzzhu и квадраты
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Jzzhu есть два целых числа n и m. Он называет целочисленную точку (x, y) плоскости специальной, если 0 ≤ x ≤ n и 0 ≤ y ≤ m. Единичным квадратом Jzzhu называет квадрат, углы которого находятся в точках (x, y), (x + 1, y), (x + 1, y + 1), (x, y + 1), где x и y некоторые целые числа.

Рассмотрим все квадраты (их стороны не обязательно параллельны осям координат), углы которых являются специальными точками. Для каждого такого квадрата Jzzhu нарисовал по точке во всех единичных квадратах, которые находятся целиком внутри него. В итоге некоторые единичные квадраты могут содержать несколько точек. Теперь ему интересно, сколько всего точек на плоскости он нарисовал. Найдите остаток от деления этого числа на 1000000007 (109 + 7).

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

В первой строке записано целое число t (1 ≤ t ≤ 105) — количество тестов.

В каждой из следующих t строк записано описание очередного теста: два целых числа n и m (1 ≤ n, m ≤ 106) — параметры задачи для текущего теста.

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

Для каждого теста выведите суммарное количество точек, которое нарисует Jzzhu.

Примеры
Входные данные
4
1 3
2 2
2 5
3 4
Выходные данные
3
8
26
58