Ціле додатнє число \textbf{n }можна записати у вигляді суми різних натуральних чисел декількома способами. Наприклад, для \textbf{n }= \textbf{5 }існує \textbf{3 }способи: \textbf{5}, \textbf{2+3}, \textbf{1+4}. для \textbf{n }= \textbf{6 }існує \textbf{4 }способи: \textbf{6}, \textbf{1+5}, \textbf{1+2+3}, \textbf{2+4}. У цій задачі перестановка одних і тих же чисел вважається одним способом, тобто \textbf{1+2+3} теж саме, що \textbf{2+1+3} або \textbf{3+1+2} і т.д. \InputFile У першому рядку задано кількість тестів t (\textbf{1 }≤ \textbf{t }≤ \textbf{20}). Наступні \textbf{t }рядків містять самі тестові випадки у вигляді єдиного числа \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{2000}). \OutputFile Для кожного заданого числа n виведіть у окремому рядку кількість різних способів подання заданого числа у вигляді суми натуральних чисел, як це описано вище. Так як шукане число може бути достатньо великим, відповідь виведіть за модулем \textbf{100999}.