시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 1024 MB32181352.000%

문제

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$

예제 입력 1

3
1 3 2

예제 출력 1

0
20
6