격자 위의 직선

$n \times n$ 크기의 정수 격자가 주어졌다고 하자. 예를 들어 $\{(i, j)\}_{i=0, j=0}^{n-1, n-1}$과 같은 격자이다. $l_n$을 격자 위의 점 중 적어도 두 점을 지나는 서로 다른 직선의 개수라고 하자.

$n = 3$일 때, 아래 그림과 같이 이런 직선은 정확히 20개이다.

주어진 모든 $n$에 대해 $l_n$을 구하시오.

첫째 줄에 질의의 개수 $Q$가 주어진다. 둘째 줄에는 공백으로 구분된 정수 $n_1, \dots, n_Q$가 주어진다.

$Q$개의 수 $l_{n_1}, \dots, l_{n_Q}$를 각각 한 줄에 하나씩 출력한다. $l_k$는 클 수 있으므로 각 값을 $10^6 + 3$으로 나눈 나머지를 출력한다.

$1 \le Q \le 1000$

$1 \le n_i \le 10^7$