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