학급 짝짓기

헥토르의 학급에는 N명의 학생이 있고, N은 짝수입니다. 헥토르는 다가오는 학년에 누가 누구와 같은 책상에 나란히 앉게 될지 궁금합니다.

학생 전체를 둘씩 짝지을 수 있는 서로 다른 방법은 모두 몇 가지일까요?

어떤 학생이 한 방법에서 짝이 된 상대가 다른 방법에서 짝이 된 상대와 다르다면(즉, 학생 중 적어도 한 명이라도 짝이 달라지면), 두 방법을 서로 다른 것으로 봅니다.

첫째 줄에 테스트 케이스의 수 Z ($1 \le Z \le 10$)가 주어집니다. 이어서 Z개의 테스트 케이스가 주어집니다.

각 테스트 케이스는 한 줄로 이루어지며, 학급의 학생 수를 나타내는 짝수인 자연수 N ($2 \le N \le 10^6$, N은 짝수)이 주어집니다.

각 테스트 케이스마다 학생들을 둘씩 짝지을 수 있는 서로 다른 방법의 수를 구하세요. 이 값은 매우 커질 수 있으므로 $1000$으로 나눈 나머지를 출력합니다. 각 결과는 한 줄에 하나씩 출력합니다.