시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 128 31 29 31.183%

문제

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

꿍이 경매하는 부동산들은 한 줄로 연속적으로 나열된 집들인데, 편의상 맨 왼쪽부터 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+XHVjNzc0XHViNTRjLCBLXHViYzg4XHVjOWQxXHVjNzQwIEsrMSBcdWM2ZDBcdWM3NTggXHVhYzAwXHVhY2E5XHVjNWQwIFx1YjA5OVx1Y2MzMFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZmNkXHVjNzQwIFx1YzViNFx1YjVhNCBcdWMxOTBcdWIyZDhcdWM3NzQgTlx1YzZkMFx1Yzc0NCBcdWFjMTZcdWFjZTAgXHVjNzg4XHViMmU0XHViYTc0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWM5ZDFcdWI0ZTRcdWM3NTggXHVhYzAwXHVhY2E5IFx1ZDU2OVx1Yzc3NCBOXHVjNmQwXHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWIwOTlcdWNjMzBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWQwZGRcdWMwYWNcdWQ1NmRcdWI0ZTRcdWM3NDQgXHViOWQwXHVkNTc0XHVjOTAwXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1YjRcdWI1YTQgXHVjMTkwXHViMmQ4XHVjNzc0IDVcdWM2ZDBcdWM3NDQgXHVhYzE2XHVhY2UwIFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWFmY2RcdWM3NDAgXHVjNzc0IFx1YzE5MFx1YjJkOFx1YzVkMFx1YWM4YyAxXHViYzg4XHVjOWQxXHVhY2ZjIDJcdWJjODhcdWM5ZDEoXHVhYzAxXHVhYzAxIDJcdWM2ZDBcdWFjZmMgM1x1YzZkMClcdWM3NDQgXHViMDk5XHVjYzMwXHViYzFiXHViM2M0XHViODVkIFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWIyZThcdWMyMWNcdWQ3ODggNFx1YmM4OFx1YzlkMSg1XHVjNmQwKVx1Yzc0NCBcdWIwOTlcdWNjMzBcdWJjMWJcdWFjOGMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3NzQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDJcdWFjMDBcdWM5YzBcdWM3NTggXHVjMTIwXHVkMGRkXHVjMGFjXHVkNTZkXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZmNkXHVjNzQwIFx1YWMwOFx1YzIxOFx1Yjg1ZCBcdWM3MjBcdWJhODVcdWQ1NzRcdWM4MzggXHVjNzc0XHVjODFjIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWMxMjBcdWQwZGRcdWMwYWNcdWQ1NmRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YWUzMFx1YzVkNCBcdWJjMTRcdWMwNThcdWIyZTQuIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWFmY2RcdWM3NDQgXHVjNzA0XHVkNTc0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjMjE4IE4gKDEmbGU7TiZsZTsxLDAwMCwwMDApIFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwIFx1YzE5MFx1YjJkOFx1Yzc3NCBcdWFjMTZcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjNjOFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWM3NDAgMFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxJm5ic3A7XHVkMTRjXHVjMmE0XHVkMmI4XHVjZjE4XHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCwmbmJzcDtcdWFjMDEgXHVjOTA0XHVjNWQwIFx1YWNlMFx1YWMxZFx1Yzc3NCZuYnNwO1x1YzVmMFx1YzE4ZFx1YzgwMVx1YzczY1x1Yjg1YyBcdWIwOThcdWM1ZjRcdWI0MWMgXHVjOWQxXHVjNzQ0IFx1YjA5OVx1Y2MzMFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMjQ2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSW50ZWdlciBFc3RhdGUgQWdlbnQiLCJkZXNjcmlwdGlvbiI6IjxwPkFmdGVyIHJlY2VudCByaW90cyBpbiBGbGF0bGFuZCwgdGhlIGxlYWRlciBoYXMgZ3JhbnRlZCBwZXJtaXNzaW9uIHRvIHB1cmNoYXNlIHJlYWwgZXN0YXRlIGF0IHRoZSBmYW1vdXMgWmVybyBzdHJlZXQgdG8gZXZlcnlvbmUuIE5vdywgbm90IG9ubHkgdGhlIG5vYmxlIHBvbHlnb25zIGFyZSBhbGxvd2VkIHRvIGxpdmUgdGhlcmUsIGJ1dCBwZW50YWdvbnMsIHNxdWFyZXMsIGFuZCBldmVuIHRyaWFuZ2xlcyBhcyB3ZWxsIChpZiB0aGV5IGNhbiBhZmZvcmQgYSBob3VzZSBhdCBaZXJvIHN0cmVldCwgb2YgY291cnNlKSE8XC9wPlxyXG5cclxuPHA+QXMgYW4gZW1wbG95ZWUgb2YgdGhlICZsZHF1bztJbnRlZ2VyIEVzdGF0ZSBBZ2VuY3kmcmRxdW87LCB5b3UgYXJlIGluIGNoYXJnZSBvZiB0aGUgb25lIHNpZGUgb2YgdGhlIHN0cmVldC4gSG91c2UgbnVtYmVyaW5nIHN0YXJ0cyByaWdodCBhZnRlciBaZXJvIFNxdWFyZS4gSG91c2UgIzEgaXMgcmlnaHQgb2ZmIG9mIHRoZSBzcXVhcmUsIEhvdXNlICMyIGNvbWVzIHJpZ2h0IGFmdGVyIEhvdXNlICMxLCBIb3VzZSAjMyBjb21lcyBhZnRlciBIb3VzZSAjMiwgYW5kIHNvIG9uIHRvd2FyZHMgSW5maW5pdHkgKHdoZXJlLCBhcyBydW1vcnMgc2F5LCB0aGUgZmFtaWx5IG9mIG5vYmxlIFBlcmZlY3QgQ2lyY2xlcyBsaXZlKS4gSG91c2UgI2sgY29zdHMgZXhhY3RseSBrKzEgY29pbnMuIFRoZXJlIGlzIG5vIEhvdXNlICMwLCBzaW5jZSB0aGF0IGlzIHRoZSBzcXVhcmUuPFwvcD5cclxuXHJcbjxwPkEgcHJvbWlzaW5nIGN1c3RvbWVyIGlzIHdpbGxpbmcgdG8gc3BlbmQgZXhhY3RseSBuIGNvaW5zIHRvIHB1cmNoYXNlIGEgc2luZ2xlIGJsb2NrIG9mIGNvbnNlY3V0aXZlIGhvdXNlcyB0byBncm91cCB0b2dldGhlciBhcyBhIGNvbmRvIGNvbXBsZXguIEhvdyBtYW55IG9wdGlvbnMgZG9lcyBoZSBoYXZlPyBGb3IgZXhhbXBsZSwgaWYgaGUgd2lzaGVzIHRvIHNwZW5kIDUgY29pbnMsIGhlIG1heSBidXkgaG91c2VzICMxIGFuZCAjMiAod2hpY2ggY29zdHMgMiszPTUpLCBvciBoZSBtYXkganVzdCBidXkgaG91c2UgIzQsIHNvIGhlIGhhcyB0d28gb3B0aW9ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgc2V2ZXJhbCB0ZXN0IGNhc2VzIGluIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb25zaXN0IG9mIGEgc2luZ2xlIGludGVnZXIgbiAoMSZsZTtuJmxlOzEsMDAwLDAwMCkgb24gaXRzIG93biBsaW5lLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgY29pbnMgYSBjdXN0b21lciBpcyB3aWxsaW5nIHRvIHNwZW5kLiBUaGUgaW5wdXQgd2lsbCBlbmQgd2l0aCBhIGxpbmUgd2l0aCBhIHNpbmdsZSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGN1c3RvbWVyLCBvdXRwdXQgdGhlIG51bWJlciBvZiB3YXlzIGhlIGNhbiBidXkgY29uc2VjdXRpdmUgaG91c2VzIHNwZW5kaW5nIGV4YWN0bHkgbiBjb2lucy4gT3V0cHV0IGVhY2ggbnVtYmVyIG9uIGl0cyBvd24gbGluZSwgd2l0aCBubyBzcGFjZXMuIERvIG5vdCBwcmludCBhbnkgYmxhbmsgbGluZXMgYmV0d2VlbiBvdXRwdXRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==