서로 다른 자연수의 합

양의 정수 $N$ ($1 \le N \le 2000$)을 서로 다른 자연수의 합으로 나타내는 방법이 몇 가지인지 구한다.

한 가지 방법은 다음을 모두 지킨다.

• 합에 쓰는 자연수는 모두 서로 다르다. 같은 수를 두 번 이상 쓸 수 없다.
• 더하는 순서만 다른 두 식은 같은 방법으로 센다.
• 항이 하나뿐인 $N$ 자신도 한 가지 방법으로 센다.

$N$이 주어졌을 때 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다. 이어지는 $T$개의 줄에 각 테스트 케이스의 $N$이 하나씩 주어진다.

각 테스트 케이스마다 $N$을 서로 다른 자연수의 합으로 나타내는 방법의 수를 $100999$로 나눈 나머지를 입력 순서대로 한 줄에 하나씩 출력한다.