시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 79 42 32 76.190%

문제

피타고라스의 정리는 직각삼각형의 세 변의 관계를 나타내는 정리이다. 빗변의 길이를 C, 다른 두 변의 길이를 A, B라고 한다면 다음과 같은 식으로 쓸 수 있다.

A2 + B2 = C2

세 변의 길이가 모두 자연수인 직각삼각형 중에 가장 유명한 삼각형은 아래와 같다.

A = 12인 경우에는 다음과 같이 두 개의 직사각형을 찾을 수 있다.

A가 주어졌을 때, 빗변의 길이 C가 자연수인 직각삼각형을 만드는 자연수 B (B > A)는 몇 개가 있을까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 자연수 A (2 ≤ A < 220)이 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

입력으로 주어진 A에 대해서, 빗변의 길이가 자연수인 직각삼각형을 만드는 B(B>A)의 개수를 출력한다.

예제 입력 1

3
12
2
1048574
1048575
0

예제 출력 1

1
2
0
1
175
W3sicHJvYmxlbV9pZCI6IjQ1NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YWNcdWJjYTRcdWM5YzAgXHVjNjI0XHViZTBjIFx1ZDUzY1x1ZDBjMFx1YWNlMFx1Yjc3Y1x1YzJhNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTNjXHVkMGMwXHVhY2UwXHViNzdjXHVjMmE0XHVjNzU4IFx1YzgxNVx1YjlhY1x1YjI5NCBcdWM5YzFcdWFjMDFcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjMTM4IFx1YmNjMFx1Yzc1OCBcdWFkMDBcdWFjYzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YjlhY1x1Yzc3NFx1YjJlNC4gXHViZTU3XHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBDLCBcdWIyZTRcdWI5NzggXHViNDUwIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgQSwgQlx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNGY4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+QTxzdXA+MjxcL3N1cD4gKyBCPHN1cD4yPFwvc3VwPiA9IEM8c3VwPjI8XC9zdXA+PFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjMTM4IFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHViYWE4XHViNDUwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3OCBcdWM5YzFcdWFjMDFcdWMwYmNcdWFjMDFcdWQ2MTUgXHVjOTExXHVjNWQwIFx1YWMwMFx1YzdhNSBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9weXRhMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjhweDsgd2lkdGg6MTY0cHhcIiBcLz48XC9wPlxyXG5cclxuXHJcblxyXG48cD5BID0gMTJcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9weXRhMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjhweDsgd2lkdGg6NTczcHhcIiBcLz48XC9wPlxyXG5cclxuXHJcblxyXG48cD5BXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmU1N1x1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzQgQ1x1YWMwMCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzggXHVjOWMxXHVhYzAxXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggQiAoQiAmZ3Q7IEEpXHViMjk0IFx1YmE4NyBcdWFjMWNcdWFjMDAgXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1Yzc5MFx1YzVmMFx1YzIxOCBBICgyICZsZTsgQSAmbHQ7IDI8c3VwPjIwPFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBBXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViZTU3XHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzggXHVjOWMxXHVhYzAxXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBCKEImZ3Q7QSlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NTYzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHl0aGFnb3JhcydzIFJldmVuZ2UiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBmYW1vdXMgUHl0aGFnb3JlYW4gdGhlb3JlbSBzdGF0ZXMgdGhhdCBhIHJpZ2h0IHRyaWFuZ2xlLCBoYXZpbmcgc2lkZSBsZW5ndGhzIEEgYW5kIEIgYW5kIGh5cG90ZW51c2UgbGVuZ3RoIEMsIHNhdGlzZmllcyB0aGUgZm9ybXVsYTxcL3A+XHJcblxyXG48cD5BPHN1cD4yPFwvc3VwPiArIEI8c3VwPjI8XC9zdXA+ID0gQzxzdXA+MjxcL3N1cD48XC9wPlxyXG5cclxuPHA+SXQgaXMgYWxzbyB3ZWxsIGtub3duIHRoYXQgdGhlcmUgZXhpc3Qgc29tZSByaWdodCB0cmlhbmdsZXMgaW4gd2hpY2ggYWxsIHRocmVlIHNpZGUgbGVuZ3RocyBhcmUgaW50ZWdyYWwsIHN1Y2ggYXMgdGhlIGNsYXNzaWM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcHl0YTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTI4cHg7IHdpZHRoOjE2NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZ1cnRoZXIgZXhhbXBsZXMsIGJvdGggaGF2aW5nIEE9MTIsIGFyZSB0aGUgZm9sbG93aW5nOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3B5dGEyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyOHB4OyB3aWR0aDo1NzNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgcXVlc3Rpb24gb2YgdGhlIGRheSBpcywgZ2l2ZW4gYSBmaXhlZCBpbnRlZ2VyIHZhbHVlIGZvciBBLCBob3cgbWFueSBkaXN0aW5jdCBpbnRlZ2VycyBCICZndDsgQSBleGlzdCBzdWNoIHRoYXQgdGhlIGh5cG90ZW51c2UgbGVuZ3RoIEMgaXMgaW50ZWdyYWw/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBBLCBzdWNoIHRoYXQgMiAmbGU7IEEgJmx0OyAxMDQ4NTc2ID0gMjxzdXA+MjA8XC9zdXA+LiBUaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBkZXNpZ25hdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHRoZSB2YWx1ZSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHZhbHVlIG9mIEEsIG91dHB1dCB0aGUgbnVtYmVyIG9mIGludGVnZXJzIEIgJmd0OyBBIHN1Y2ggdGhhdCBhIHJpZ2h0IHRyaWFuZ2xlIGhhdmluZyBzaWRlIGxlbmd0aHMgQSBhbmQgQiBoYXMgYSBoeXBvdGVudXNlIHdpdGggaW50ZWdyYWwgbGVuZ3RoLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5PdXIgaGludCBpcyB0aGF0IHlvdSBuZWVkIG5vdCBjb25zaWRlciBhbnkgdmFsdWUgZm9yIEIgdGhhdCBpcyBncmVhdGVyIHRoYW4gKEE8c3VwPjI8XC9zdXA+LTEpXC8yLCBiZWNhdXNlIGZvciBhbnkgc3VjaCByaWdodCB0cmlhbmdsZSwgaHlwb3RlbnVzZSBDIHNhdGlzZmllcyBCICZsdDsgQyAmbHQ7IEIgKyAxLCBhbmQgdGh1cyBjYW5ub3QgaGF2ZSBpbnRlZ3JhbCBsZW5ndGguPFwvcD5cclxuXHJcbjxwPk91ciB3YXJuaW5nIGlzIHRoYXQgZm9yIHZhbHVlcyBvZiBBICZhc3ltcDsgMjxzdXA+MjA8XC9zdXA+LCB0aGVyZSBjb3VsZCBiZSBzb2x1dGlvbnMgd2l0aCBCICZhc3ltcDsgMjxzdXA+Mzk8XC9zdXA+LCBhbmQgdGh1cyB2YWx1ZXMgb2YgQzxzdXA+MjxcL3N1cD4gJmd0OyBCPHN1cD4yPFwvc3VwPiAmYXN5bXA7IDI8c3VwPjc4PFwvc3VwPi48XC9wPlxyXG5cclxuPHA+WW91IGNhbiBndWFyYW50ZWUgeW91cnNlbGYgNjQtYml0IGludGVnZXIgY2FsY3VsYXRpb25zIGJ5IHVzaW5nIHRoZSB0eXBlIGxvbmcgbG9uZyBpbiBDKysgb3IgbG9uZyBpbiBKYXZhLiBCdXQgbmVpdGhlciBvZiB0aG9zZSB0eXBlcyB3aWxsIGFsbG93IHlvdSB0byBhY2N1cmF0ZWx5IGNhbGN1bGF0ZSB0aGUgdmFsdWUgb2YgQzIgZm9yIHN1Y2ggYW4gZXh0cmVtZSBjYXNlLiAoV2hpY2ggaXMsIGFmdGVyIGFsbCwgd2hhdCBtYWtlcyB0aGlzIFB5dGhhZ29yYXMmIzM5O3MgcmV2ZW5nZSEpPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=