Сумма различными числами

Целое положительное число n можно записать в виде суммы различных натуральных чисел несколькими способами. Например,

для n = 5 существует 3 способа: 5, 2+3, 1+4.

для n = 6, существует 4 способа: 6, 1+5, 1+2+3, 2+4.

В этой задаче перестановка одних и тех же чисел считается одним способом, т.е. 1+2+3 тоже самое, что 2+1+3 или 3+1+2 и т.д.

Входные данные

В первой строке задано количество тестов t (1 ≤ t ≤ 20). Следующие t строк содержат сами тесты в виде единственного числа n (1 ≤ n ≤ 2000).

Выходные данные

Для каждого заданного числа n выведите в отдельной строке количество различных способов представления заданного числа в виде суммы натуральных чисел, как описано выше. Так как искомое число может быть достаточно большим, ответ выведите по модулю 100999.

Примеры