Lines in a grid

Suppose that we are given a $n × n$ integer grid, e.g. $\\{(i, j)\\}\_{i=0, j=0}^{n-1, n-1}$. Let $l\_n$ be the number of different lines that intersect with at least two points on the grid.

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

Compute $l\_n$ for all given $n$.

First line contains an integer $Q$ – the number of queries. The second line contains $Q$ space-separated integers $n\_1, \dots , n\_Q$.

Print $Q$ numbers $l\_{n\_1} , \dots , l\_{n\_N}$, each in its own line. Since $l\_k$ can be large, print them modulo $10^6 + 3$.

• $1 ≤ Q ≤ 1000$
• $1 ≤ n\_i ≤ 10^7$