题目描述

Panda 先生最近迷上了一款名为 Square Off 的新游戏，玩家需要在一个均匀间隔的矩形点阵中找出尽可能多的不同正方形。要找到一个正方形，玩家必须找出四个点，它们构成一个正方形的顶点。正方形的每条边的长度必须相等（当然，具体长度无关紧要），并且正方形不一定需要与网格的坐标轴对齐。玩家每找到这样一个不同的正方形，即可获得 1 分。两个正方形不同，当且仅当它们对应的四个点的集合不同。

Panda 先生拿到了一张由 $R$ 行 $C$ 列点组成的网格。请问他在这个网格中能找到多少个不同的正方形？由于答案可能非常大，请输出它对 $10^9 + 7$（即 $1000000007$）取模的结果。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行，每行包含两个整数 $R$ 和 $C$，分别表示网格中每行的点数和每列的点数。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是网格中可以找到的不同正方形的数量。

4
2 4
3 4
4 4
1000 500

Case #1: 3
Case #2: 10
Case #3: 20
Case #4: 624937395

提示

下图展示了前三个样例的网格，以及第三个样例中的一个有效正方形。

:::align{center}

:::

限制条件

$1 \le T \le 100$。

小数据集（测试集 1 – 可见）

$2 \le R \le 1000$。

$2 \le C \le 1000$。

大数据集（测试集 2 – 隐藏）

$2 \le R \le 10^9$。

$2 \le C \le 10^9$。

翻译由 DeepSeek V4 Pro 完成