시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 117 25 24 28.916%

문제

꿍은 꿍만의 독특한 경매방식으로 부동산 경매업계에서 꽤나 유명한 인물이다.

꿍이 경매하는 부동산들은 한 줄로 연속적으로 나열된 집들인데, 편의상 맨 왼쪽부터 1번집, 2번집... 이라고 부른다고 하자. (0번집은 존재하지 않으며 집은 무한히 많다고 가정한다.)

이 때, K번집은 K+1 원의 가격에 낙찰된다.

꿍은 어떤 손님이 N원을 갖고 있다면 연속된 집들의 가격 합이 N원이 되도록 낙찰받을 수 있는 선택사항들을 말해준다. 예를 들어, 어떤 손님이 5원을 갖고 있다면 꿍은 이 손님에게 1번집과 2번집(각각 2원과 3원)을 낙찰받도록 하거나 단순히 4번집(5원)을 낙찰받게 할 수 있다. 따라서 이 경우에는 2가지의 선택사항이 존재한다.

꿍은 갈수록 유명해져 이제 이러한 선택사항의 수를 계산하기엔 바쁘다. 여러분이 꿍을 위해 프로그램을 만들어주자.

입력

각 테스트 케이스는 하나의 정수 N (1≤N≤1,000,000) 으로 이루어져 있으며 손님이 갖고 있는 돈을 나타낸다.

입력의 끝은 0으로 주어진다.

출력

각 테스트켘이스에 대해, 각 줄에 고객이 연속적으로 나열된 집을 낙찰받을 수 있는 경우의 수를 출력한다.

예제 입력 1

1
2
5
0

예제 출력 1

0
1
2
W3sicHJvYmxlbV9pZCI6IjEwMjQ2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZDgwXHViM2Q5XHVjMGIwIFx1YWNiZFx1YjllNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZmNkXHVjNzQwIFx1YWZjZFx1YjljY1x1Yzc1OCBcdWIzYzVcdWQyYjlcdWQ1NWMgXHVhY2JkXHViOWU0XHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YmQ4MFx1YjNkOVx1YzBiMCBcdWFjYmRcdWI5ZTRcdWM1YzVcdWFjYzRcdWM1ZDBcdWMxMWMgXHVhZjY0XHViMDk4IFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWM3NzhcdWJiM2NcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWZjZFx1Yzc3NCBcdWFjYmRcdWI5ZTRcdWQ1NThcdWIyOTQgXHViZDgwXHViM2Q5XHVjMGIwXHViNGU0XHVjNzQwJm5ic3A7XHVkNTVjIFx1YzkwNFx1Yjg1YyZuYnNwO1x1YzVmMFx1YzE4ZFx1YzgwMVx1YzczY1x1Yjg1YyZuYnNwO1x1YjA5OFx1YzVmNFx1YjQxYyBcdWM5ZDFcdWI0ZTRcdWM3NzhcdWIzNzAsIFx1ZDNiOFx1Yzc1OFx1YzBjMSBcdWI5ZTggXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIDFcdWJjODhcdWM5ZDEsIDJcdWJjODhcdWM5ZDEuLi4gXHVjNzc0XHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuICgwXHViYzg4XHVjOWQxXHVjNzQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAgXHVjOWQxXHVjNzQwIFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWI5Y2VcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjU0YywgS1x1YmM4OFx1YzlkMVx1Yzc0MCBLKzEgXHVjNmQwXHVjNzU4IFx1YWMwMFx1YWNhOVx1YzVkMCBcdWIwOTlcdWNjMzBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWZjZFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHVjMTkwXHViMmQ4XHVjNzc0IE5cdWM2ZDBcdWM3NDQgXHVhYzE2XHVhY2UwIFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVjOWQxXHViNGU0XHVjNzU4IFx1YWMwMFx1YWNhOSBcdWQ1NjlcdWM3NzQgTlx1YzZkMFx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQgXHViMDk5XHVjYzMwXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTIwXHVkMGRkXHVjMGFjXHVkNTZkXHViNGU0XHVjNzQ0IFx1YjlkMFx1ZDU3NFx1YzkwMFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNWI0XHViNWE0IFx1YzE5MFx1YjJkOFx1Yzc3NCA1XHVjNmQwXHVjNzQ0IFx1YWMxNlx1YWNlMCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZmNkXHVjNzQwIFx1Yzc3NCBcdWMxOTBcdWIyZDhcdWM1ZDBcdWFjOGMgMVx1YmM4OFx1YzlkMVx1YWNmYyAyXHViYzg4XHVjOWQxKFx1YWMwMVx1YWMwMSAyXHVjNmQwXHVhY2ZjIDNcdWM2ZDApXHVjNzQ0IFx1YjA5OVx1Y2MzMFx1YmMxYlx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWFjNzBcdWIwOTggXHViMmU4XHVjMjFjXHVkNzg4IDRcdWJjODhcdWM5ZDEoNVx1YzZkMClcdWM3NDQgXHViMDk5XHVjYzMwXHViYzFiXHVhYzhjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAyXHVhYzAwXHVjOWMwXHVjNzU4IFx1YzEyMFx1ZDBkZFx1YzBhY1x1ZDU2ZFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWZjZFx1Yzc0MCBcdWFjMDhcdWMyMThcdWI4NWQgXHVjNzIwXHViYTg1XHVkNTc0XHVjODM4IFx1Yzc3NFx1YzgxYyBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMTIwXHVkMGRkXHVjMGFjXHVkNTZkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWFlMzBcdWM1ZDQgXHViYzE0XHVjMDU4XHViMmU0LiBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NzQgXHVhZmNkXHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0XHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOCBOICgxJmxlO04mbGU7MSwwMDAsMDAwKSBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCBcdWMxOTBcdWIyZDhcdWM3NzQgXHVhYzE2XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWIzYzhcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViMDVkXHVjNzQwIDBcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSZuYnNwO1x1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YxOFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsJm5ic3A7XHVhYzAxIFx1YzkwNFx1YzVkMCBcdWFjZTBcdWFjMWRcdWM3NzQmbmJzcDtcdWM1ZjBcdWMxOGRcdWM4MDFcdWM3M2NcdWI4NWMgXHViMDk4XHVjNWY0XHViNDFjIFx1YzlkMVx1Yzc0NCBcdWIwOTlcdWNjMzBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDI0NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkludGVnZXIgRXN0YXRlIEFnZW50IiwiZGVzY3JpcHRpb24iOiI8cD5BZnRlciByZWNlbnQgcmlvdHMgaW4gRmxhdGxhbmQsIHRoZSBsZWFkZXIgaGFzIGdyYW50ZWQgcGVybWlzc2lvbiB0byBwdXJjaGFzZSByZWFsIGVzdGF0ZSBhdCB0aGUgZmFtb3VzIFplcm8gc3RyZWV0IHRvIGV2ZXJ5b25lLiBOb3csIG5vdCBvbmx5IHRoZSBub2JsZSBwb2x5Z29ucyBhcmUgYWxsb3dlZCB0byBsaXZlIHRoZXJlLCBidXQgcGVudGFnb25zLCBzcXVhcmVzLCBhbmQgZXZlbiB0cmlhbmdsZXMgYXMgd2VsbCAoaWYgdGhleSBjYW4gYWZmb3JkIGEgaG91c2UgYXQgWmVybyBzdHJlZXQsIG9mIGNvdXJzZSkhPFwvcD5cclxuXHJcbjxwPkFzIGFuIGVtcGxveWVlIG9mIHRoZSAmbGRxdW87SW50ZWdlciBFc3RhdGUgQWdlbmN5JnJkcXVvOywgeW91IGFyZSBpbiBjaGFyZ2Ugb2YgdGhlIG9uZSBzaWRlIG9mIHRoZSBzdHJlZXQuIEhvdXNlIG51bWJlcmluZyBzdGFydHMgcmlnaHQgYWZ0ZXIgWmVybyBTcXVhcmUuIEhvdXNlICMxIGlzIHJpZ2h0IG9mZiBvZiB0aGUgc3F1YXJlLCBIb3VzZSAjMiBjb21lcyByaWdodCBhZnRlciBIb3VzZSAjMSwgSG91c2UgIzMgY29tZXMgYWZ0ZXIgSG91c2UgIzIsIGFuZCBzbyBvbiB0b3dhcmRzIEluZmluaXR5ICh3aGVyZSwgYXMgcnVtb3JzIHNheSwgdGhlIGZhbWlseSBvZiBub2JsZSBQZXJmZWN0IENpcmNsZXMgbGl2ZSkuIEhvdXNlICNrIGNvc3RzIGV4YWN0bHkgaysxIGNvaW5zLiBUaGVyZSBpcyBubyBIb3VzZSAjMCwgc2luY2UgdGhhdCBpcyB0aGUgc3F1YXJlLjxcL3A+XHJcblxyXG48cD5BIHByb21pc2luZyBjdXN0b21lciBpcyB3aWxsaW5nIHRvIHNwZW5kIGV4YWN0bHkgbiBjb2lucyB0byBwdXJjaGFzZSBhIHNpbmdsZSBibG9jayBvZiBjb25zZWN1dGl2ZSBob3VzZXMgdG8gZ3JvdXAgdG9nZXRoZXIgYXMgYSBjb25kbyBjb21wbGV4LiBIb3cgbWFueSBvcHRpb25zIGRvZXMgaGUgaGF2ZT8gRm9yIGV4YW1wbGUsIGlmIGhlIHdpc2hlcyB0byBzcGVuZCA1IGNvaW5zLCBoZSBtYXkgYnV5IGhvdXNlcyAjMSBhbmQgIzIgKHdoaWNoIGNvc3RzIDIrMz01KSwgb3IgaGUgbWF5IGp1c3QgYnV5IGhvdXNlICM0LCBzbyBoZSBoYXMgdHdvIG9wdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSB3aWxsIGJlIHNldmVyYWwgdGVzdCBjYXNlcyBpbiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHdpbGwgY29uc2lzdCBvZiBhIHNpbmdsZSBpbnRlZ2VyIG4gKDEmbGU7biZsZTsxLDAwMCwwMDApIG9uIGl0cyBvd24gbGluZSwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIGNvaW5zIGEgY3VzdG9tZXIgaXMgd2lsbGluZyB0byBzcGVuZC4gVGhlIGlucHV0IHdpbGwgZW5kIHdpdGggYSBsaW5lIHdpdGggYSBzaW5nbGUgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjdXN0b21lciwgb3V0cHV0IHRoZSBudW1iZXIgb2Ygd2F5cyBoZSBjYW4gYnV5IGNvbnNlY3V0aXZlIGhvdXNlcyBzcGVuZGluZyBleGFjdGx5IG4gY29pbnMuIE91dHB1dCBlYWNoIG51bWJlciBvbiBpdHMgb3duIGxpbmUsIHdpdGggbm8gc3BhY2VzLiBEbyBub3QgcHJpbnQgYW55IGJsYW5rIGxpbmVzIGJldHdlZW4gb3V0cHV0cy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=