KKKCT2 - Counting Triangles 2

This is a new version of problem CT with the new limit: X, Y <= 10000, and the result will be written in modulo 2009

Input

The input begins with C – number of test cases. Each test case consists of X, Y.

Output

For each test case, output the result in a line.

Limit

C <= 200
0 <= X, Y <= 10000

Example

Input:
2
0 3
1 1

Output:
0
4

Added by:Alex & Friends
Date:2010-03-26
Time limit:0.406s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:From CT problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.