시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 559 355 255 64.557%

문제

양의 정수는 많아야 4개의 제곱수로 표현할 수 있다고 한다. 이 이론을 라그랑주의 네 제곱수 정리라고 한다. 이 정리는 조제프루이 라그랑주가 1770년에 증명했다.

우리는 이 이론을 증명하거나 새로운 이론을 발견할 필요는 없고, n이 주어졌을 때 4개 이하의 제곱수의 합으로 n을 만들 수 있는 경우의 수를 구하려고 한다. 경우의 수를 구할 때 제곱수의 순서가 바뀌는 경우는 같은 경우로 본다. 따라서 32 + 42 과 42 + 32는 같은 경우이다.

N이 25일 때 4개 이하의 제곱수의 합으로 표현 할 수 있는 경우는 12 + 22 + 22 + 42, 32 + 42, 52 이렇게 3가지이다.

입력

입력은 최대 255줄이다. 각 줄에는 215보다 작은 양의 정수가 하나씩 주어진다. 마지막 줄에는 0이 하나 있고, 입력 데이터가 아니다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 n을 많아야 4개의 제곱수로 나타내는 경우의 수를 출력한다.

예제 입력 1

1
25
2003
211
20007
0

예제 출력 1

1
3
48
7
738

힌트

W3sicHJvYmxlbV9pZCI6IjM5MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3N2NcdWFkZjhcdWI3OTFcdWM4ZmNcdWM3NTggXHViMTI0IFx1YzgxY1x1YWNmMVx1YzIxOCBcdWM4MTVcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWIyOTQgXHViOWNlXHVjNTQ0XHVjNTdjIDRcdWFjMWNcdWM3NTggXHVjODFjXHVhY2YxXHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1Yzc3NFx1Yjg2MFx1Yzc0NCA8YSBocmVmPVwiaHR0cDpcL1wvZW4ud2lraXBlZGlhLm9yZ1wvd2lraVwvTGFncmFuZ2UlMjdzX2ZvdXItc3F1YXJlX3RoZW9yZW1cIj5cdWI3N2NcdWFkZjhcdWI3OTFcdWM4ZmNcdWM3NTggXHViMTI0IFx1YzgxY1x1YWNmMVx1YzIxOCBcdWM4MTVcdWI5YWM8XC9hPlx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWI5YWNcdWIyOTQgXHVjODcwXHVjODFjXHVkNTA0XHViOGU4XHVjNzc0IFx1Yjc3Y1x1YWRmOFx1Yjc5MVx1YzhmY1x1YWMwMCAxNzcwXHViMTQ0XHVjNWQwIFx1Yzk5ZFx1YmE4NVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzc0IFx1Yzc3NFx1Yjg2MFx1Yzc0NCBcdWM5OWRcdWJhODVcdWQ1NThcdWFjNzBcdWIwOTggXHVjMGM4XHViODVjXHVjNmI0IFx1Yzc3NFx1Yjg2MFx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1NjAgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YWNlMCwgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIDRcdWFjMWMgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxY1x1YWNmMVx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgblx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTYwIFx1YjU0YyBcdWM4MWNcdWFjZjFcdWMyMThcdWM3NTggXHVjMjFjXHVjMTFjXHVhYzAwIFx1YmMxNFx1YjAwY1x1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1Yjg1YyBcdWJjZjhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyAzPHN1cD4yPFwvc3VwPiArIDQ8c3VwPjI8XC9zdXA+IFx1YWNmYyA0PHN1cD4yPFwvc3VwPiArIDM8c3VwPjI8XC9zdXA+XHViMjk0IFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+Tlx1Yzc3NCAyNVx1Yzc3YyBcdWI1NGMgNFx1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODFjXHVhY2YxXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IDE8c3VwPjI8XC9zdXA+ICsgMjxzdXA+MjxcL3N1cD4gKyAyPHN1cD4yPFwvc3VwPiArIDQ8c3VwPjI8XC9zdXA+LCAzPHN1cD4yPFwvc3VwPiArIDQ8c3VwPjI8XC9zdXA+LCA1PHN1cD4yPFwvc3VwPiBcdWM3NzRcdWI4MDdcdWFjOGMgM1x1YWMwMFx1YzljMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWNkNWNcdWIzMDAgMjU1XHVjOTA0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IDI8c3VwPjE1PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YWNlMCwgXHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgblx1Yzc0NCBcdWI5Y2VcdWM1NDRcdWM1N2MgNFx1YWMxY1x1Yzc1OCBcdWM4MWNcdWFjZjFcdWMyMThcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5MzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYWdyYW5nZVx1MjAxOXMgRm91ci1TcXVhcmUgVGhlb3JlbSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGZhY3QgdGhhdCBhbnkgcG9zaXRpdmUgaW50ZWdlciBoYXMgYSByZXByZXNlbnRhdGlvbiBhcyB0aGUgc3VtIG9mIGF0IG1vc3QgZm91ciBwb3NpdGl2ZSBzcXVhcmVzIChpLmUuIHNxdWFyZXMgb2YgcG9zaXRpdmUgaW50ZWdlcnMpIGlzIGtub3duIGFzIExhZ3JhbmdlJnJzcXVvO3MgRm91ci1TcXVhcmUgVGhlb3JlbS4gVGhlIFx1ZmIwMXJzdCBwdWJsaXNoZWQgcHJvb2Ygb2YgdGhlIHRoZW9yZW0gd2FzIGdpdmVuIGJ5IEpvc2VwaC1Mb3VpcyBMYWdyYW5nZSBpbiAxNzcwLiBZb3VyIG1pc3Npb24gaG93ZXZlciBpcyBub3QgdG8gZXhwbGFpbiB0aGUgb3JpZ2luYWwgcHJvb2Ygbm9yIHRvIGRpc2NvdmVyIGEgbmV3IHByb29mIGJ1dCB0byBzaG93IHRoYXQgdGhlIHRoZW9yZW0gaG9sZHMgZm9yIHNvbWUgc3BlY2lcdWZiMDFjIG51bWJlcnMgYnkgY291bnRpbmcgaG93IG1hbnkgc3VjaCBwb3NzaWJsZSByZXByZXNlbnRhdGlvbnMgdGhlcmUgYXJlLjxcL3A+XHJcblxyXG48cD5Gb3IgYSBnaXZlbiBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHlvdSBzaG91bGQgcmVwb3J0IHRoZSBudW1iZXIgb2YgYWxsIHJlcHJlc2VudGF0aW9ucyBvZiBuIGFzIHRoZSBzdW0gb2YgYXQgbW9zdCBmb3VyIHBvc2l0aXZlIHNxdWFyZXMuIFRoZSBvcmRlciBvZiBhZGRpdGlvbiBkb2VzIG5vdCBtYXR0ZXIsIGUuZy4geW91IHNob3VsZCBjb25zaWRlciA0PHN1cD4yPFwvc3VwPiArIDM8c3VwPjI8XC9zdXA+IGFuZCAzPHN1cD4yPFwvc3VwPiArIDQ8c3VwPjI8XC9zdXA+IGFyZSB0aGUgc2FtZSByZXByZXNlbnRhdGlvbi48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGxldCZyc3F1bztzIGNoZWNrIHRoZSBjYXNlIG9mIDI1LiBUaGlzIGludGVnZXIgaGFzIGp1c3QgdGhyZWUgcmVwcmVzZW50YXRpb25zIDE8c3VwPjI8XC9zdXA+KzI8c3VwPjI8XC9zdXA+KzI8c3VwPjI8XC9zdXA+KzQ8c3VwPjI8XC9zdXA+LCAzPHN1cD4yPFwvc3VwPiArIDQ8c3VwPjI8XC9zdXA+LCBhbmQgNTxzdXA+MjxcL3N1cD4uIFRodXMgeW91IHNob3VsZCByZXBvcnQgMyBpbiB0aGlzIGNhc2UuIEJlIGNhcmVmdWwgbm90IHRvIGNvdW50IDQ8c3VwPjI8XC9zdXA+ICsgMzxzdXA+MjxcL3N1cD4gYW5kIDM8c3VwPjI8XC9zdXA+ICsgNDxzdXA+MjxcL3N1cD4gc2VwYXJhdGVseS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBjb21wb3NlZCBvZiBhdCBtb3N0IDI1NSBsaW5lcywgZWFjaCBjb250YWluaW5nIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbGVzcyB0aGFuIDI8c3VwPjE1PFwvc3VwPiwgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgemVyby4gVGhlIGxhc3QgbGluZSBpcyBub3QgYSBwYXJ0IG9mIHRoZSBpbnB1dCBkYXRhLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGJlIGNvbXBvc2VkIG9mIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlci4gTm8gb3RoZXIgY2hhcmFjdGVycyBzaG91bGQgYXBwZWFyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuXHJcbjxwPlRoZSBvdXRwdXQgaW50ZWdlciBjb3JyZXNwb25kaW5nIHRvIHRoZSBpbnB1dCBpbnRlZ2VyIG4gaXMgdGhlIG51bWJlciBvZiBhbGwgcmVwcmVzZW50YXRpb25zIG9mIG4gYXMgdGhlIHN1bSBvZiBhdCBtb3N0IGZvdXIgcG9zaXRpdmUgc3F1YXJlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=