시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 128 MB69139629860.816%

문제

양의 정수 N (1 ≤ N ≤ 2000)을 서로 다른 자연수의 합으로 나타내는 방법은 여러 가지가 있다.

예를 들어, N = 5인 경우 N = 5 = 2 + 3 = 1 + 4로 총 3가지 방법이 있다. 1 + 1 + 3에서 1은 여러 번 등장하기 때문에 세지 않고, 2 + 3과 3 + 2는 순서만 바뀐 것이기 때문에 같은 것으로 센다.

또, N = 6인 경우에는 N = 6 = 1 + 5 = 1 + 2 + 3 = 2 + 4로 총 4가지 방법이 있다.

N이 주어졌을 때, 서로 다른 자연수의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에, 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다.

출력

각 테스트 케이스마다 N을 서로 다른 자연수의 합으로 나타내는 방법의 수 100999로 나눈 나머지를 출력한다.

예제 입력 1

4
5
6
10
200

예제 출력 1

3
4
10
50568
W3sicHJvYmxlbV9pZCI6Ijk3NjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWQ1NjkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAyMDAwKVx1Yzc0NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTiA9IDVcdWM3NzggXHVhY2JkXHVjNmIwIE4gPSA1ID0gMiArIDMgPSAxICsgNFx1Yjg1YyBcdWNkMWQgM1x1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNzg4XHViMmU0LiAxICsgMSArIDNcdWM1ZDBcdWMxMWMgMVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMTM4XHVjOWMwIFx1YzU0YVx1YWNlMCwgMiArIDNcdWFjZmMgMyArIDJcdWIyOTQgXHVjMjFjXHVjMTFjXHViOWNjIFx1YmMxNFx1YjAxMCBcdWFjODNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWMxOVx1Yzc0MCBcdWFjODNcdWM3M2NcdWI4NWMgXHVjMTNjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI2MTAsIE4gPSA2XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBOID0gNiA9IDEgKyA1ID0gMSArIDIgKyAzID0gMiArIDRcdWI4NWMgXHVjZDFkIDRcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICgxICZsZTsgVCAmbGU7IDIwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgTlx1Yzc0NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMTggMTAwOTk5XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiA8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5NzY0IiwicHJvYmxlbV9sYW5nIjoiNyIsInRpdGxlIjoiXHUwZTFjXHUwZTI1XHUwZTFhXHUwZTI3XHUwZTAxXHUwZTQwXHUwZTI1XHUwZTAyXHUwZTQ0XHUwZTIxXHUwZTQ4XHUwZTBiIFx1MGU0OVx1MGUzMiAoRGVjb21wKSIsImRlc2NyaXB0aW9uIjoiPHA+XHUwZTQzXHUwZTJiXHUwZTQ5XHUwZTA4IFx1MGUzMlx1MGUxOVx1MGUyN1x1MGUxOVx1MGU0MFx1MGUxNVx1MGU0N1x1MGUyMSBOICgxICZsdDs9IE4gJmx0Oz0gMiwwMDApIFx1MGUyZFx1MGUyMlx1MGUzMlx1MGUwMVx1MGUxN1x1MGUyM1x1MGUzMlx1MGUxYVx1MGUyN1x1MGU0OFx1MGUzMiBOIFx1MGUyYVx1MGUzMlx1MGUyMVx1MGUzMlx1MGUyM1x1MGUxNlx1MGU0MFx1MGUwMlx1MGUzNVx1MGUyMlx1MGUxOVx1MGU0MFx1MGUxYlx1MGU0N1x1MGUxOVx1MGUxY1x1MGUyNVx1MGUxYVx1MGUyN1x1MGUwMVx1MGUwMlx1MGUyZFx1MGUwN1x1MGUwOCBcdTBlMzJcdTBlMTlcdTBlMjdcdTBlMTlcdTBlNDBcdTBlMTVcdTBlNDdcdTBlMjFcdTBlMTdcdTBlMzVcdTBlNDhcdTBlMjFcdTBlMzVcdTBlMDRcdTBlNDhcdTBlMzJcdTBlNDRcdTBlMjFcdTBlNDhcdTBlMGJcdTBlNDkgXHUwZTMyXHUwZTAxXHUwZTMxXHUwZTE5XHUwZTQwXHUwZTI1XHUwZTIyXHUwZTQ0XHUwZTE0XHUwZTQ5XHUwZTAxXHUwZTM1XHUwZTQ4XHUwZTQxXHUwZTFhXHUwZTFhJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1MGUxNVx1MGUzMVx1MGUyN1x1MGUyZFx1MGUyMlx1MGU0OFx1MGUzMlx1MGUwN1x1MGU0MFx1MGUwYVx1MGU0OFx1MGUxOSBcdTBlMTZcdTBlNDlcdTBlMzIgTj01IFx1MGU0MFx1MGUyM1x1MGUzMlx1MGUyYVx1MGUzMlx1MGUyMVx1MGUzMlx1MGUyM1x1MGUxNlx1MGU0MFx1MGUwMlx1MGUzNVx1MGUyMlx1MGUxOSBOIFx1MGU0NFx1MGUxNFx1MGU0OSAzIFx1MGU0MVx1MGUxYVx1MGUxYSBcdTBlMDRcdTBlMzdcdTBlMmQgNSwgMiszIFx1MGU0MVx1MGUyNVx1MGUzMCAxKzQgXHUwZTJhXHUwZTMxXHUwZTA3XHUwZTQwXHUwZTAxXHUwZTE1XHUwZTI3XHUwZTQ4XHUwZTMyXHUwZTQwXHUwZTIzXHUwZTMyXHUwZTA4XHUwZTMwXHUwZTQ0XHUwZTIxXHUwZTQ4XHUwZTE5XHUwZTMxXHUwZTFhIDErMSszIFx1MGU0MFx1MGUxZVx1MGUyM1x1MGUzMlx1MGUzMFx1MGUyN1x1MGU0OFx1MGUzMlx1MGUyMVx1MGUzNVx1MGUwMVx1MGUzMlx1MGUyM1x1MGU0M1x1MGUwYVx1MGU0OSAxIFx1MGUwYlx1MGU0OSBcdTBlMzJcdTBlMDFcdTBlMzFcdTBlMTkgXHUwZTE5XHUwZTJkXHUwZTAxXHUwZTA4XHUwZTMyXHUwZTAxXHUwZTE5XHUwZTM1XHUwZTQ5IFx1MGU0MFx1MGUyM1x1MGUzMlx1MGUyMlx1MGUzMVx1MGUwN1x1MGUxZVx1MGUzNFx1MGUwOFx1MGUzMlx1MGUyM1x1MGUxM1x1MGUzMlx1MGUyN1x1MGU0OFx1MGUzMiAyKzMgXHUwZTAxXHUwZTMxXHUwZTFhIDMrMiBcdTBlMTlcdTBlMzFcdTBlNDlcdTBlMTlcdTBlNDBcdTBlMWJcdTBlNDdcdTBlMTlcdTBlMjdcdTBlMzRcdTBlMThcdTBlMzVcdTBlNDBcdTBlMDJcdTBlMzVcdTBlMjJcdTBlMTlcdTBlNDBcdTBlMTRcdTBlMzVcdTBlMjJcdTBlMjdcdTBlMDFcdTBlMzFcdTBlMTlcdTBlMTRcdTBlNDlcdTBlMjdcdTBlMjIgKFx1MGUxOVx1MGUzMVx1MGU0OFx1MGUxOVx1MGUwNFx1MGUzN1x1MGUyZFx1MGUwOFx1MGUzMFx1MGU0NFx1MGUyMVx1MGU0OFx1MGUxOVx1MGUzMVx1MGUxYVx1MGUwYlx1MGU0OSBcdTBlMzIpJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1MGUxZVx1MGUzNFx1MGUwOFx1MGUzMlx1MGUyM1x1MGUxM1x1MGUzMlx1MGUxNVx1MGUzMVx1MGUyN1x1MGUyZFx1MGUyMlx1MGU0OFx1MGUzMlx1MGUwN1x1MGUxN1x1MGUzNVx1MGU0OFx1MGUyYVx1MGUyZFx1MGUwNyBcdTBlNDBcdTBlMjFcdTBlMzdcdTBlNDhcdTBlMmQgTj02IFx1MGU0MFx1MGUyM1x1MGUzMlx1MGUyYVx1MGUzMlx1MGUyMVx1MGUzMlx1MGUyM1x1MGUxNlx1MGU0MFx1MGUwMlx1MGUzNVx1MGUyMlx1MGUxOSBOIFx1MGU0NFx1MGUxNFx1MGU0OSA0IFx1MGU0MVx1MGUxYVx1MGUxYVx1MGUwNFx1MGUzN1x1MGUyZCA2LCAxKzUsIDErMiszIFx1MGU0MVx1MGUyNVx1MGUzMCAyKzQmbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1MGUxYVx1MGUyM1x1MGUyM1x1MGUxN1x1MGUzMVx1MGUxNFx1MGU0MVx1MGUyM1x1MGUwMVx1MGUyM1x1MGUzMFx1MGUxYVx1MGUzOFx1MGUwOCBcdTBlMzJcdTBlMTlcdTBlMjdcdTBlMTlcdTBlNDBcdTBlMTVcdTBlNDdcdTBlMjEgVCBcdTBlNDFcdTBlMTdcdTBlMTlcdTBlMDggXHUwZTMyXHUwZTE5XHUwZTI3XHUwZTE5XHUwZTAyXHUwZTQ5XHUwZTJkXHUwZTIxXHUwZTM5XHUwZTI1XHUwZTE3XHUwZTE0XHUwZTJhXHUwZTJkXHUwZTFhICgxICZsdDs9IFQgJmx0Oz0gMjApIFx1MGUwOFx1MGUzMlx1MGUwMVx1MGUxOVx1MGUzMVx1MGU0OVx1MGUxOVx1MGUyZFx1MGUzNVx1MGUwMSBUIFx1MGUxYVx1MGUyM1x1MGUyM1x1MGUxN1x1MGUzMVx1MGUxNFx1MGUwOFx1MGUzMFx1MGUyM1x1MGUzMFx1MGUxYVx1MGUzOCBcdTBlMDJcdTBlNDlcdTBlMmRcdTBlMjFcdTBlMzlcdTBlMjVcdTBlMTdcdTBlMTRcdTBlMmFcdTBlMmRcdTBlMWFcdTBlNDFcdTBlMTVcdTBlNDhcdTBlMjVcdTBlMzBcdTBlMGFcdTBlMzhcdTBlMTQgXHUwZTBhXHUwZTM4XHUwZTE0XHUwZTI1XHUwZTMwXHUwZTJiXHUwZTE5XHUwZTM2XHUwZTQ4XHUwZTA3XHUwZTFhXHUwZTIzXHUwZTIzXHUwZTE3XHUwZTMxXHUwZTE0IFx1MGUwMlx1MGU0OVx1MGUyZFx1MGUyMVx1MGUzOVx1MGUyNVx1MGUxN1x1MGUxNFx1MGUyYVx1MGUyZFx1MGUxYVx1MGU0MVx1MGUxNVx1MGU0OFx1MGUyNVx1MGUzMFx1MGUwYVx1MGUzOFx1MGUxNFx1MGUwOFx1MGUzMFx1MGUyM1x1MGUzMFx1MGUxYVx1MGUzOFx1MGUwOCBcdTBlMzJcdTBlMTlcdTBlMjdcdTBlMTlcdTBlNDBcdTBlMTVcdTBlNDdcdTBlMjEgTiBcdTBlMmJcdTBlMTlcdTBlMzZcdTBlNDhcdTBlMDdcdTBlMTVcdTBlMzFcdTBlMjcmbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTBlMmEgXHUwZTMyXHUwZTJiXHUwZTIzXHUwZTMxXHUwZTFhXHUwZTQxXHUwZTE1XHUwZTQ4XHUwZTI1XHUwZTMwXHUwZTAyXHUwZTQ5XHUwZTJkXHUwZTIxXHUwZTM5XHUwZTI1XHUwZTBhXHUwZTM4XHUwZTE0XHUwZTE3XHUwZTE0XHUwZTJhXHUwZTJkXHUwZTFhIFx1MGU0M1x1MGUyYlx1MGU0OVx1MGUxZVx1MGUzNFx1MGUyMVx1MGUxZVx1MGU0Y1x1MGUwOCBcdTBlMzJcdTBlMTlcdTBlMjdcdTBlMTlcdTBlMjdcdTBlMzRcdTBlMThcdTBlMzVcdTBlMTdcdTBlMzVcdTBlNDhcdTBlMmFcdTBlMzJcdTBlMjFcdTBlMzJcdTBlMjNcdTBlMTZcdTBlNDBcdTBlMDJcdTBlMzVcdTBlMjJcdTBlMTkgTiBcdTBlNDNcdTBlMmJcdTBlNDlcdTBlNDBcdTBlMWJcdTBlNDdcdTBlMTlcdTBlMWNcdTBlMjVcdTBlMWFcdTBlMjdcdTBlMDFcdTBlMTdcdTBlMzVcdTBlNDhcdTBlNDFcdTBlMTVcdTBlNDhcdTBlMjVcdTBlMzBcdTBlMWVcdTBlMDhcdTBlMTlcdTBlNGNcdTBlMjFcdTBlMzVcdTBlMDRcdTBlNDhcdTBlMzJcdTBlNDRcdTBlMjFcdTBlNDggXHUwZTBiXHUwZTQ5IFx1MGUzMlx1MGUwMVx1MGUzMVx1MGUxOSBcdTBlNDBcdTBlMTlcdTBlMzdcdTBlNDhcdTBlMmRcdTBlMDdcdTBlMDhcdTBlMzJcdTBlMDFcdTBlMDQgXHUwZTMyXHUwZTE1XHUwZTJkXHUwZTFhXHUwZTJkXHUwZTMyXHUwZTA4XHUwZTIxXHUwZTM1XHUwZTA0XHUwZTQ4XHUwZTMyXHUwZTIxXHUwZTMyXHUwZTAxIFx1MGU0M1x1MGUyYlx1MGU0OVx1MGUxZVx1MGUzNFx1MGUyMVx1MGUxZVx1MGU0Y1x1MGUwNCBcdTBlMzJcdTBlMTVcdTBlMmRcdTBlMWEgbW9kdWxvIDEwMDk5OSZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IlRoYWkifV0=