假设我们有一个 $n \times n$ 的整数网格，例如 $\{(i, j)\}_{i=0, j=0}^{n-1, n-1}$。令 $l_n$ 为与网格中至少两个点相交的不同直线的数量。
对于 $n = 3$，恰好有 20 条这样的直线，如下图所示。
计算所有给定 $n$ 的 $l_n$。
输入格式
第一行包含一个整数 $Q$，表示查询次数。第二行包含 $Q$ 个以空格分隔的整数 $n_1, \dots, n_Q$。
数据范围
- $1 \le Q \le 1000$
- $1 \le n_i \le 10^7$
输出格式
输出 $Q$ 个数字 $l_{n_1}, \dots, l_{n_Q}$，每个数字占一行。由于 $l_k$ 可能非常大，请输出它们对 $10^6 + 3$ 取模的结果。
样例
样例输入 1
3 1 3 2
样例输出 1
0 20 6