25108번 - 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$

힌트