# Arup Guha
# 7/22/2013
# Solution to 2013 SI@UCF Contest Question: Combos

MODVAL = 32003

def main():

    # Set up list to store all answers.
    ans = [0]*16000
    ans[0] = 1

    # Fill in answers. Note for a given n, the answer is
    # (n-1)*(n-3)*...*1 mod 32003. Item 1 can be paired with
    # n-1 other items, for each of these, require that we pair
    # the minimal numbered item next. This can be done in n-3 ways,
    # and so forth.
    for i in range(3, 32000, 2):
        ans[i//2] = (ans[i//2-1]*i)%MODVAL

    # Open input file.
    myFile = open("combos.in", "r")
    numCases = int(myFile.readline())

    # Read input and display stored output.
    for i in range(numCases):
        inputVal = int(myFile.readline())
        print(ans[inputVal//2-1])

    # Close file.
    myFile.close()

main()