SPOJ in Gyumri

   A positive integer N can be written in the form of sum of distinct positive integers in several ways. For example,

      N=5, there are 3 ways: 5, 2+3, 1+4

      N=6, there are 4 ways: 6, 1+5, 1+2+3, 2+4

   Here the permutation of the same elements is counted as one i.e. 1+2+3 is the same as 2+1+3 and 3+1+2, etc.

Input

   You are given the number of test cases (1 <= T <= 20) in the first line. Then, in the following T lines, each line contains the number N (1 <= N <= 2,000).

Output

   Print out, for each number N, the number of possible ways of writing that number in the form of sum of distinct numbers as described above. In order to limit the range of answers, the answer must be the result value modulo 100999.

Examples