Problems
Sum of Distinct Numbers
Sum of Distinct Numbers
A positive integer \textbf{n }can be written in the form of sum of distinct positive integers in several ways. For example,
\textbf{n} = \textbf{5}, there are \textbf{3 }ways: \textbf{5}, \textbf{2+3}, \textbf{1+4}.
\textbf{n} = \textbf{6}, there are \textbf{4 }ways: \textbf{6}, \textbf{1+5}, \textbf{1+2+3}, \textbf{2+4}.
Here the permutation of the same elements is counted as one i.e. \textbf{1+2+3} is the same as \textbf{2+1+3} and \textbf{3+1+2}, etc.
\InputFile
You are given the number of test cases \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{20}) in the first line. Then, in the following \textbf{t} lines, each line contains the number \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{2000}).
\OutputFile
Print for each number \textbf{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 \textbf{100999}.
Input example #1
4 5 6 10 200
Output example #1
3 4 10 50568