← 返回题目列表

Codeforces · 449/E

E. Jzzhu 和 Squares

中文机器翻译题面 查看原题

Jzzhu 有两个整数,n 和 m。如果 0 ≤ x ≤ n 且 0 ≤ y ≤ m,他将平面上的整数点 (x, y) 称为特殊点。 Jzzhu 将单位正方形定义为角点为 (x, y)、(x + 1, y)、(x + 1, y + 1)、(x, y + 1) 的正方形,其中 x 和 y 是一些整数。

让我们看看所有在特殊点处有角的正方形(它们的边不一定平行于坐标轴)。对于每个这样的正方形,Jzzhu 在完全位于其内部的每个单位正方形中绘制一个点。之后,一些单位方块可以包含多个点。现在Jzzhu想知道,他在平面上画了多少个点。求这个数模 1000000007 (109 + 7)。

输入

第一行包含一个整数 t (1 ≤ t ≤ 105) — 测试次数。

接下来的 t 行中的每一行都包含测试的描述:两个整数 n 和 m (1 ≤ n, m ≤ 106) — 当前测试的变量值。

输出

对于每个测试输出,总点数以 1000000007 (109 + 7) 为模。

示例

输入 #1

4
1 3
2 2
2 5
3 4

输出 #1

3
8
26
58