시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 128 MB 340 199 133 58.590%

문제

양의 정수 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+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgTlx1Yzc0NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMTggMTAwOTk5XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk3NjQiLCJwcm9ibGVtX2xhbmciOiI3IiwidGl0bGUiOiJcdTBlMWNcdTBlMjVcdTBlMWFcdTBlMjdcdTBlMDFcdTBlNDBcdTBlMjVcdTBlMDJcdTBlNDRcdTBlMjFcdTBlNDhcdTBlMGIgXHUwZTQ5XHUwZTMyIiwiZGVzY3JpcHRpb24iOiI8cD5cdTBlNDNcdTBlMmJcdTBlNDlcdTBlMDggXHUwZTMyXHUwZTE5XHUwZTI3XHUwZTE5XHUwZTQwXHUwZTE1XHUwZTQ3XHUwZTIxIE4gKDEgJmx0Oz0gTiAmbHQ7PSAyLDAwMCkgXHUwZTJkXHUwZTIyXHUwZTMyXHUwZTAxXHUwZTE3XHUwZTIzXHUwZTMyXHUwZTFhXHUwZTI3XHUwZTQ4XHUwZTMyIE4gXHUwZTJhXHUwZTMyXHUwZTIxXHUwZTMyXHUwZTIzXHUwZTE2XHUwZTQwXHUwZTAyXHUwZTM1XHUwZTIyXHUwZTE5XHUwZTQwXHUwZTFiXHUwZTQ3XHUwZTE5XHUwZTFjXHUwZTI1XHUwZTFhXHUwZTI3XHUwZTAxXHUwZTAyXHUwZTJkXHUwZTA3XHUwZTA4IFx1MGUzMlx1MGUxOVx1MGUyN1x1MGUxOVx1MGU0MFx1MGUxNVx1MGU0N1x1MGUyMVx1MGUxN1x1MGUzNVx1MGU0OFx1MGUyMVx1MGUzNVx1MGUwNFx1MGU0OFx1MGUzMlx1MGU0NFx1MGUyMVx1MGU0OFx1MGUwYlx1MGU0OSBcdTBlMzJcdTBlMDFcdTBlMzFcdTBlMTlcdTBlNDBcdTBlMjVcdTBlMjJcdTBlNDRcdTBlMTRcdTBlNDlcdTBlMDFcdTBlMzVcdTBlNDhcdTBlNDFcdTBlMWFcdTBlMWEmbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuXHUwZTE1XHUwZTMxXHUwZTI3XHUwZTJkXHUwZTIyXHUwZTQ4XHUwZTMyXHUwZTA3XHUwZTQwXHUwZTBhXHUwZTQ4XHUwZTE5IFx1MGUxNlx1MGU0OVx1MGUzMiBOPTUgXHUwZTQwXHUwZTIzXHUwZTMyXHUwZTJhXHUwZTMyXHUwZTIxXHUwZTMyXHUwZTIzXHUwZTE2XHUwZTQwXHUwZTAyXHUwZTM1XHUwZTIyXHUwZTE5IE4gXHUwZTQ0XHUwZTE0XHUwZTQ5IDMgXHUwZTQxXHUwZTFhXHUwZTFhIFx1MGUwNFx1MGUzN1x1MGUyZCA1LCAyKzMgXHUwZTQxXHUwZTI1XHUwZTMwIDErNCBcdTBlMmFcdTBlMzFcdTBlMDdcdTBlNDBcdTBlMDFcdTBlMTVcdTBlMjdcdTBlNDhcdTBlMzJcdTBlNDBcdTBlMjNcdTBlMzJcdTBlMDhcdTBlMzBcdTBlNDRcdTBlMjFcdTBlNDhcdTBlMTlcdTBlMzFcdTBlMWEgMSsxKzMgXHUwZTQwXHUwZTFlXHUwZTIzXHUwZTMyXHUwZTMwXHUwZTI3XHUwZTQ4XHUwZTMyXHUwZTIxXHUwZTM1XHUwZTAxXHUwZTMyXHUwZTIzXHUwZTQzXHUwZTBhXHUwZTQ5IDEgXHUwZTBiXHUwZTQ5IFx1MGUzMlx1MGUwMVx1MGUzMVx1MGUxOSBcdTBlMTlcdTBlMmRcdTBlMDFcdTBlMDhcdTBlMzJcdTBlMDFcdTBlMTlcdTBlMzVcdTBlNDkgXHUwZTQwXHUwZTIzXHUwZTMyXHUwZTIyXHUwZTMxXHUwZTA3XHUwZTFlXHUwZTM0XHUwZTA4XHUwZTMyXHUwZTIzXHUwZTEzXHUwZTMyXHUwZTI3XHUwZTQ4XHUwZTMyIDIrMyBcdTBlMDFcdTBlMzFcdTBlMWEgMysyIFx1MGUxOVx1MGUzMVx1MGU0OVx1MGUxOVx1MGU0MFx1MGUxYlx1MGU0N1x1MGUxOVx1MGUyN1x1MGUzNFx1MGUxOFx1MGUzNVx1MGU0MFx1MGUwMlx1MGUzNVx1MGUyMlx1MGUxOVx1MGU0MFx1MGUxNFx1MGUzNVx1MGUyMlx1MGUyN1x1MGUwMVx1MGUzMVx1MGUxOVx1MGUxNFx1MGU0OVx1MGUyN1x1MGUyMiAoXHUwZTE5XHUwZTMxXHUwZTQ4XHUwZTE5XHUwZTA0XHUwZTM3XHUwZTJkXHUwZTA4XHUwZTMwXHUwZTQ0XHUwZTIxXHUwZTQ4XHUwZTE5XHUwZTMxXHUwZTFhXHUwZTBiXHUwZTQ5IFx1MGUzMikmbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuXHUwZTFlXHUwZTM0XHUwZTA4XHUwZTMyXHUwZTIzXHUwZTEzXHUwZTMyXHUwZTE1XHUwZTMxXHUwZTI3XHUwZTJkXHUwZTIyXHUwZTQ4XHUwZTMyXHUwZTA3XHUwZTE3XHUwZTM1XHUwZTQ4XHUwZTJhXHUwZTJkXHUwZTA3IFx1MGU0MFx1MGUyMVx1MGUzN1x1MGU0OFx1MGUyZCBOPTYgXHUwZTQwXHUwZTIzXHUwZTMyXHUwZTJhXHUwZTMyXHUwZTIxXHUwZTMyXHUwZTIzXHUwZTE2XHUwZTQwXHUwZTAyXHUwZTM1XHUwZTIyXHUwZTE5IE4gXHUwZTQ0XHUwZTE0XHUwZTQ5IDQgXHUwZTQxXHUwZTFhXHUwZTFhXHUwZTA0XHUwZTM3XHUwZTJkIDYsIDErNSwgMSsyKzMgXHUwZTQxXHUwZTI1XHUwZTMwIDIrNCZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1MGUxYVx1MGUyM1x1MGUyM1x1MGUxN1x1MGUzMVx1MGUxNFx1MGU0MVx1MGUyM1x1MGUwMVx1MGUyM1x1MGUzMFx1MGUxYVx1MGUzOFx1MGUwOCBcdTBlMzJcdTBlMTlcdTBlMjdcdTBlMTlcdTBlNDBcdTBlMTVcdTBlNDdcdTBlMjEgVCBcdTBlNDFcdTBlMTdcdTBlMTlcdTBlMDggXHUwZTMyXHUwZTE5XHUwZTI3XHUwZTE5XHUwZTAyXHUwZTQ5XHUwZTJkXHUwZTIxXHUwZTM5XHUwZTI1XHUwZTE3XHUwZTE0XHUwZTJhXHUwZTJkXHUwZTFhICgxICZsdDs9IFQgJmx0Oz0gMjApIFx1MGUwOFx1MGUzMlx1MGUwMVx1MGUxOVx1MGUzMVx1MGU0OVx1MGUxOVx1MGUyZFx1MGUzNVx1MGUwMSBUIFx1MGUxYVx1MGUyM1x1MGUyM1x1MGUxN1x1MGUzMVx1MGUxNFx1MGUwOFx1MGUzMFx1MGUyM1x1MGUzMFx1MGUxYVx1MGUzOCBcdTBlMDJcdTBlNDlcdTBlMmRcdTBlMjFcdTBlMzlcdTBlMjVcdTBlMTdcdTBlMTRcdTBlMmFcdTBlMmRcdTBlMWFcdTBlNDFcdTBlMTVcdTBlNDhcdTBlMjVcdTBlMzBcdTBlMGFcdTBlMzhcdTBlMTQgXHUwZTBhXHUwZTM4XHUwZTE0XHUwZTI1XHUwZTMwXHUwZTJiXHUwZTE5XHUwZTM2XHUwZTQ4XHUwZTA3XHUwZTFhXHUwZTIzXHUwZTIzXHUwZTE3XHUwZTMxXHUwZTE0IFx1MGUwMlx1MGU0OVx1MGUyZFx1MGUyMVx1MGUzOVx1MGUyNVx1MGUxN1x1MGUxNFx1MGUyYVx1MGUyZFx1MGUxYVx1MGU0MVx1MGUxNVx1MGU0OFx1MGUyNVx1MGUzMFx1MGUwYVx1MGUzOFx1MGUxNFx1MGUwOFx1MGUzMFx1MGUyM1x1MGUzMFx1MGUxYVx1MGUzOFx1MGUwOCBcdTBlMzJcdTBlMTlcdTBlMjdcdTBlMTlcdTBlNDBcdTBlMTVcdTBlNDdcdTBlMjEgTiBcdTBlMmJcdTBlMTlcdTBlMzZcdTBlNDhcdTBlMDdcdTBlMTVcdTBlMzFcdTBlMjcmbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHUwZTJhIFx1MGUzMlx1MGUyYlx1MGUyM1x1MGUzMVx1MGUxYVx1MGU0MVx1MGUxNVx1MGU0OFx1MGUyNVx1MGUzMFx1MGUwMlx1MGU0OVx1MGUyZFx1MGUyMVx1MGUzOVx1MGUyNVx1MGUwYVx1MGUzOFx1MGUxNFx1MGUxN1x1MGUxNFx1MGUyYVx1MGUyZFx1MGUxYSBcdTBlNDNcdTBlMmJcdTBlNDlcdTBlMWVcdTBlMzRcdTBlMjFcdTBlMWVcdTBlNGNcdTBlMDggXHUwZTMyXHUwZTE5XHUwZTI3XHUwZTE5XHUwZTI3XHUwZTM0XHUwZTE4XHUwZTM1XHUwZTE3XHUwZTM1XHUwZTQ4XHUwZTJhXHUwZTMyXHUwZTIxXHUwZTMyXHUwZTIzXHUwZTE2XHUwZTQwXHUwZTAyXHUwZTM1XHUwZTIyXHUwZTE5IE4gXHUwZTQzXHUwZTJiXHUwZTQ5XHUwZTQwXHUwZTFiXHUwZTQ3XHUwZTE5XHUwZTFjXHUwZTI1XHUwZTFhXHUwZTI3XHUwZTAxXHUwZTE3XHUwZTM1XHUwZTQ4XHUwZTQxXHUwZTE1XHUwZTQ4XHUwZTI1XHUwZTMwXHUwZTFlXHUwZTA4XHUwZTE5XHUwZTRjXHUwZTIxXHUwZTM1XHUwZTA0XHUwZTQ4XHUwZTMyXHUwZTQ0XHUwZTIxXHUwZTQ4IFx1MGUwYlx1MGU0OSBcdTBlMzJcdTBlMDFcdTBlMzFcdTBlMTkgXHUwZTQwXHUwZTE5XHUwZTM3XHUwZTQ4XHUwZTJkXHUwZTA3XHUwZTA4XHUwZTMyXHUwZTAxXHUwZTA0IFx1MGUzMlx1MGUxNVx1MGUyZFx1MGUxYVx1MGUyZFx1MGUzMlx1MGUwOFx1MGUyMVx1MGUzNVx1MGUwNFx1MGU0OFx1MGUzMlx1MGUyMVx1MGUzMlx1MGUwMSBcdTBlNDNcdTBlMmJcdTBlNDlcdTBlMWVcdTBlMzRcdTBlMjFcdTBlMWVcdTBlNGNcdTBlMDQgXHUwZTMyXHUwZTE1XHUwZTJkXHUwZTFhIG1vZHVsbyAxMDA5OTkmbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkMGRjXHVhZDZkXHVjNWI0In1d