题目描述

考虑一个二维整数网格，左下角为 $(0,0)$，右上角为 $(X,Y)$。网格点是所有坐标均为整数的点。

我们关心三个顶点均位于网格点上的 等腰直角三角形。

请计算这样的三角形一共有多少个。

由于答案可能很大，请输出答案对 $2009$ 取模后的结果。

输入格式

第一行一个整数 $C$，表示测试用例数量。

接下来 $C$ 行，每行两个整数 $X,Y$，表示网格矩形的右上角坐标。

输出格式

对于每个测试用例，输出一行一个整数，表示等腰直角三角形数量对 $2009$ 取模后的结果。

数据范围

• $C\le 200$
• $0\le X,Y\le 10000$

样例

2
0 3
1 1

0
4