Lines in a grid

Time limit8sMemory limit1024 MB

Summary

Count the distinct lines through at least two points of an n by n integer grid for each query n, modulo 1000003.

Level: Medium7 of 10
Topics: Math, Number theory, Combinatorics
Solved: No attempts yet

Problem

Suppose that we are given an $n \times n$ integer grid, for example $\{(i, j)\}_{i=0, j=0}^{n-1, n-1}$ . Let $l_n$ be the number of different lines that intersect at least two points of the grid.

For $n = 3$ , there are exactly 20 such lines, as drawn in the image below.

Compute $l_n$ for all given $n$ .

Input

The first line contains an integer $Q$ , the number of queries. The second line contains $Q$ space-separated integers $n_1, \dots, n_Q$ .

Output

Print $Q$ numbers $l_{n_1}, \dots, l_{n_Q}$ , each on its own line. Since $l_k$ can be large, print each value modulo $10^6 + 3$ .

Constraints

$1 \le Q \le 1000$

$1 \le n_i \le 10^7$

Examples1

Example 1
Input
```
3
1 3 2
```
Expected output
```
0
20
6
```