Solve the query ,

given f(0)=0 , f(1)=1 , f(2)=1

f(n) = f(n-2) + f(n-3) + n*2

Input

First line denotes the number of test cases T

T lines follow each containing a number n

Output

Output T lines, As the number can be very large, output the answer modulo 10000003.

Constraints

1< t ≤1000

1< n ≤10^9

SAMPLE INPUT
3
2
6
17

SAMPLE OUTPUT
1
29
1067

见题面

见题面