DETER - Find The Determinant

In this problem you have to calculate the determinant of an N x N matrix whose entries are given by m[i][j] = gcd(i,j), 1 ≤ i,j ≤ N.

Here gcd(i,j) denotes the greatest common divisor of i and j.

As the determinant D can grow very large, you have to print D%1000003.

Input

First line of input consists of a single integer containing the number of test cases T ( equal to around 500000), each of the following T lines contain an integer N the size of the matrix. N lies between 1 and 2000000 ( both inclusive ).

Output

One line corresponding to each test case containing the determinant modulo 1000003 for the corresponding test case.

Example

Input:
3
1
3
5

Output:
1
2
16

Added by:Ajay Somani
Date:2007-09-01
Time limit:1s
Source limit:2048B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:"The Art Of Computer Programming"

hide comments
2011-11-29 19:58:01 BugsBunny :)
:(
2009-04-10 03:28:19 [Trichromatic] XilinX
This problem is moved to tutorial section because a similar (almost the same) problem MSE08H is available in the classical section.
2009-03-31 15:59:01 Ajay Somani
second.
2009-03-18 17:03:27 ~!(*(@*!@^&
In which book? 1st, 2nd ...?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.