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