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

Được gửi lên bởi:Alex & Friends
Ngày:2010-03-26
Thời gian chạy:0.120s-0.730s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:From CT problem

hide comments
2011-06-24 15:01:32 Tmbao
Cách mình đã là O(min(x , y) * t) rồi , Time hơi tệ :((
2011-06-17 08:47:01 Noyethug
Quen la' O(x*t) hoac O(y*t)
2011-06-17 08:46:28 Noyethug
uhm
cach' O(1)......ma' chjnh xac la' O(n*t)........:D
2010-05-01 00:52:11 Trần Hải Ðãng
Buồn cười quá bài này làm mãi nhìn thấy dữ kiện chia cho 2009 hj hj hj, thực ra không cần vì kết quả trong phạm vi longint thôi, ai có cách O(1) post đi
2010-04-05 05:04:54 Nguyễn Ngọc Anh
Bài này có cách làm O(1) :)
2010-04-03 01:31:46 Alex & Friends
Sao hả anh :D
2010-04-01 16:49:34 dhkhtn
new version???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.