Codeforces Round 257 (Div. 1) |
---|
Закончено |
У 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
Название |
---|