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

Ціле додатнє число 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.

Приклади