시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 206 123 91 68.421%

문제

대부분의 양의 정수는 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있다.

예를 들면 다음과 같다.

6 = 1 + 2 + 3

9 = 5 + 4 = 4 + 3 + 2

하지만, 8은 연속된 자연수 합으로 나타낼 수가 없다.

자연수 N이 주어졌을 때, 이 수를 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 출력하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 2^31보다 작다.

출력

각 테스트 케이스에 대해서 N을 적어도 2개 이상의 연속된 자연수의 합으로 나타내는 경우의 수를 출력한다.

예제 입력 1

7
6
9
8
1800
987654321
987654323
987654325

예제 출력 1

1
2
0
8
17
1
23
W3sicHJvYmxlbV9pZCI6IjI3MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjBcdWMxOGQgXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWIzMDBcdWJkODBcdWJkODRcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgMlx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVjNWYwXHVjMThkXHViNDFjIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdDYgPSAxICsgMiArIDM8XC9wPlxyXG48cD5cclxuXHQ5ID0gNSArIDQgPSA0ICsgMyArIDI8XC9wPlxyXG48cD5cclxuXHRcdWQ1NThcdWM5YzBcdWI5Y2MsIDhcdWM3NDAgXHVjNWYwXHVjMThkXHViNDFjIFx1Yzc5MFx1YzVmMFx1YzIxOCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHVjNzkwXHVjNWYwXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzIxOFx1Yjk3YyBcdWM4MDFcdWM1YjRcdWIzYzQgMlx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVjNWYwXHVjMThkXHViNDFjIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM4MTVcdWMyMTggXHVkNTU4XHViMDk4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBOXHVjNzc0XHViYTcwLCAyXjMxXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgTlx1Yzc0NCBcdWM4MDFcdWM1YjRcdWIzYzQgMlx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVjNWYwXHVjMThkXHViNDFjIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3MzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZXF1ZW5jZSBTdW0gUG9zc2liaWxpdGllcyIsImRlc2NyaXB0aW9uIjoiPHA+TW9zdCBwb3NpdGl2ZSBpbnRlZ2VycyBtYXkgYmUgd3JpdHRlbiBhcyBhIHN1bSBvZiBhIHNlcXVlbmNlIG9mIGF0IGxlYXN0IHR3byBjb25zZWN1dGl2ZSBwb3NpdGl2ZSBpbnRlZ2Vycy4gRm9yIGluc3RhbmNlLCZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjYgPSAxICsgMiArIDMmbmJzcDs8XC9saT5cclxuXHQ8bGk+OSA9IDUgKyA0ID0gMiArIDMgKyA0Jm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+YnV0IDggY2Fubm90IGJlIHNvIHdyaXR0ZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCB3aWxsIGNvbXB1dGUgaG93IG1hbnkgZGlmZmVyZW50IHdheXMgYW4gaW5wdXQgbnVtYmVyIG1heSBiZSB3cml0dGVuIGFzIGEgc3VtIG9mIGEgc2VxdWVuY2Ugb2YgYXQgbGVhc3QgdHdvIGNvbnNlY3V0aXZlIHBvc2l0aXZlIGludGVnZXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgd2lsbCBjb250YWluIHRoZSBudW1iZXIgb2YgcHJvYmxlbSBpbnN0YW5jZXMgTiBvbiBhIGxpbmUgYnkgaXRzZWxmLCAoMSAmbHQ7PSBOICZsdDs9IDEwMDApLiBUaGlzIHdpbGwgYmUgZm9sbG93ZWQgYnkgTiBsaW5lcywgb25lIGZvciBlYWNoIHByb2JsZW0gaW5zdGFuY2UuIEVhY2ggcHJvYmxlbSBsaW5lIHdpbGwgaGF2ZSB0aGUgcHJvYmxlbSBudW1iZXIsIGEgc2luZ2xlIHNwYWNlIGFuZCB0aGUgbnVtYmVyIHRvIGJlIHdyaXR0ZW4gYXMgYSBzZXF1ZW5jZSBvZiBjb25zZWN1dGl2ZSBwb3NpdGl2ZSBpbnRlZ2Vycy4gVGhlIHNlY29uZCBudW1iZXIgd2lsbCBiZSBsZXNzIHRoYW4gMl4zMSAoc28gd2lsbCBmaXQgaW4gYSAzMi1iaXQgaW50ZWdlcikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBmb3IgZWFjaCBwcm9ibGVtIGluc3RhbmNlIHdpbGwgYmUgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBwcm9ibGVtIG51bWJlciwgYSBzaW5nbGUgc3BhY2UgYW5kIHRoZSBudW1iZXIgb2Ygd2F5cyB0aGUgaW5wdXQgbnVtYmVyIGNhbiBiZSB3cml0dGVuIGFzIGEgc2VxdWVuY2Ugb2YgY29uc2VjdXRpdmUgcG9zaXRpdmUgaW50ZWdlcnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d