题目描述

Suppose that we are given a $n \times 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.

:::align{center} :::

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, \ldots, n_Q$.

输出格式

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

3
1 3 2

0
20
6

提示

Input limits

• $1 \leq Q \leq 1000$
• $1 \leq n_i \leq 10^7$