Sum of Distinct Numbers

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 t (1 ≤ t ≤ 20) in the first line. Then, in the following t lines, each line contains the number n (1 ≤ n ≤ 2000).

Output

Print 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