Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0117 - SUM OF DISTINCT NUMBERS

   A positive integer N can be written in the form of sum of distinct positive integers in several ways. For example,

      N=5, there are 3 ways: 5, 2+3, 1+4

      N=6, there are 4 ways: 6, 1+5, 1+2+3, 2+4

   Here the permutation of the same elements is counted as one i.e. 1+2+3 is the same as 2+1+3 and 3+1+2, etc.

Input

   You are given the number of test cases (1 <= T <= 20) in the first line. Then, in the following T lines, each line contains the number N (1 <= N <= 2,000).

Output

   Print out, for each number N, the number of possible ways of writing that number in the form of sum of distinct numbers as described above. In order to limit the range of answers, the answer must be the result value modulo 100999.

Examples

stdin

stdout

1

4

5

6

10

200

3

4

10

50568


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-02-01
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Thailand Southern 2013.H

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.