Sums of Distinct Natural Numbers

Count how many ways a positive integer $N$ ($1 \le N \le 2000$) can be written as a sum of distinct natural numbers.

One way obeys all of the following.

• Every natural number in the sum is different. No number may appear twice.
• Two sums that differ only in the order of the terms count as one way.
• The single-term sum $N$ itself counts as one way.

Given $N$, write a program that counts the ways.

The first line has the number of test cases $T$ ($1 \le T \le 20$). Each of the next $T$ lines has one $N$.

For each test case, print the number of ways to write $N$ as a sum of distinct natural numbers modulo $100999$, one per line, in input order.