W klasie Hektora uczy się N osób i N jest parzyste. Hektor zastanawia się kto z kim będzie siedział w ławce w nadchodzącym roku szkolnym.</p>

Na ile różnych sposobów uczniowie mogą dobrać się w pary?

Dwa sposoby uznajemy za różne jeśli co najmniej jeden uczeń w pierwszym sposobie był w parze z kimś innym niż w drugim.

입력 형식

W pierwsze linii znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10). Następnie podawane są opisy kolejnych zestawów.</p>

W pierwszej linii zestawu znajduje się liczba naturalna N ( 2 <= N <= 1000000, N parzyste ) oznaczająca liczbę uczniów w klasie.

출력 형식

Dla każdego zestawu należy obliczyć liczbę różnych sposobów dobrania uczniów w pary. Ponieważ ta liczba może być bardzo duża należy wypisać jej resztę z dzielenia przez 1000.

예제 입력

4
2
4
6
12

예제 출력

1
3
15
395