Description

假设我们有一个 $n \times n$ 的整数网格，例如 $\{(i, j)\}_{i=0, j=0}^{n-1, n-1}$。令 $l_n$ 表示与网格上至少两个点相交的不同直线的数量。

对于 $n = 3$，恰好有 $20$ 条这样的直线，如下图所示。

:::align{center} :::

请计算所有给定 $n$ 的 $l_n$。

Input Format

第一行包含一个整数 $Q$，表示询问的数量。第二行包含 $Q$ 个用空格分隔的整数 $n_1, \ldots, n_Q$。

Output Format

输出 $Q$ 行，每行一个数，依次为 $l_{n_1}, \ldots, l_{n_Q}$。由于 $l_k$ 可能很大，请对 $10^6 + 3$ 取模后输出。

3
1 3 2

0
20
6

Hint

输入范围

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

由 ChatGPT 4.1 翻译