Целое положительное число \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}.