#P16883. SPOJ Counting Triangles 2

    ID: 16093 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000提高贡献法对称性分析乘法原理分段多项式等差数列求和

SPOJ Counting Triangles 2

题目描述

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

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

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

由于答案可能很大,请输出答案对 20092009 取模后的结果。

输入格式

第一行一个整数 CC,表示测试用例数量。

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

输出格式

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

数据范围

  • C≤200C\le 200
  • 0≤X,Y≤100000\le X,Y\le 10000

样例

2
0 3
1 1
0
4