시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB91229721729.444%

문제

상근이는 삼각형을 지나칠 정도로 좋아한다. 삼각형 중에서도 직각삼각형을 좋아한다.

직각삼각형은 세 변의 길이가 양의 정수 a, b, c일 때, a ≤ b와 a2+b2 = c2을 만족하는 삼각형을 말했다.

학교에서 나머지 연산을 배운 상근이는 직각삼각형의 세 변의 관계를 나타내는 피타고라스의 정리에 나머지 연산을 적용해보기로 했다.

1보다 크거나 같고, n-1보다 작거나 같은 양의 정수 a, b, c가 있을 때, a ≤ b와 a2+b2 ≡ c2 (mod n) 을 만족하는 것의 개수를 세려고 한다.

n이 주어졌을 때, 나머지 연산을 적용한 피타고라스의 정리를 만족하는 a, b, c가 몇 개 있는지 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 n이 주어진다. (2 ≤ n ≤ 500,000)

출력

첫째 줄에 입력으로 주어진 n으로 나머지 연산을 했을 때, 피타고라스의 정리를 만족하는 a, b, c의 개수를 출력한다.

예제 입력 1

7

예제 출력 1

18

예제 입력 2

15

예제 출력 2

64
W3sicHJvYmxlbV9pZCI6IjUwNTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWQwYzBcdWFjZTBcdWI3N2NcdWMyYTRcdWM3NTggXHVjODE1XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YzljMFx1YjA5OFx1Y2U2MCBcdWM4MTVcdWIzYzRcdWI4NWMgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBcdWMwYmNcdWFjMDFcdWQ2MTUgXHVjOTExXHVjNWQwXHVjMTFjXHViM2M0IFx1YzljMVx1YWMwMVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMVx1YWMwMVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWMxMzggXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IGEsIGIsIGNcdWM3N2MgXHViNTRjLCBhICZsZTsgYlx1YzY0MCBhPHN1cD4yPFwvc3VwPitiPHN1cD4yPFwvc3VwPiA9IGM8c3VwPjI8XC9zdXA+XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWQwXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWMgXHViMDk4XHViYTM4XHVjOWMwIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWJjMzBcdWM2YjQgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzljMVx1YWMwMVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWMxMzggXHViY2MwXHVjNzU4IFx1YWQwMFx1YWNjNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVkNTNjXHVkMGMwXHVhY2UwXHViNzdjXHVjMmE0XHVjNzU4IFx1YzgxNVx1YjlhY1x1YzVkMCBcdWIwOThcdWJhMzhcdWM5YzAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzgwMVx1YzZhOVx1ZDU3NFx1YmNmNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgbi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiLCBjXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIGEgJmxlOyBiXHVjNjQwIGE8c3VwPjI8XC9zdXA+K2I8c3VwPjI8XC9zdXA+ICZlcXVpdjsgYzxzdXA+MjxcL3N1cD4gKG1vZCBuKSBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjMTM4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIwOThcdWJhMzhcdWM5YzAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzgwMVx1YzZhOVx1ZDU1YyBcdWQ1M2NcdWQwYzBcdWFjZTBcdWI3N2NcdWMyYTRcdWM3NTggXHVjODE1XHViOWFjXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBhLCBiLCBjXHVhYzAwIFx1YmE4NyBcdWFjMWMgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBuICZsZTsgNTAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgblx1YzczY1x1Yjg1YyBcdWIwOThcdWJhMzhcdWM5YzAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1ZDUzY1x1ZDBjMFx1YWNlMFx1Yjc3Y1x1YzJhNFx1Yzc1OCBcdWM4MTVcdWI5YWNcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IGEsIGIsIGNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1MDUxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSnVzdCBBIEZldyBNb3JlIFRyaWFuZ2xlcyEiLCJkZXNjcmlwdGlvbiI6IjxwPlNpbW9uIEhhcGxlcyBpcyBhIHNvbWV3aGF0IHBlY3VsaWFyIHBlcnNvbi4gTm90IHF1aXRlIGhpcCwgbm90IHF1aXRlIHNxdWFyZSwgaGUgaXMgbW9yZSBvZiBhIHRyaWFuZ3VsYXIgbmF0dXJlOiBldmVyIHNpbmNlIGNoaWxkaG9vZCwgaGUgaGFzIGhhZCBhbiBhbG1vc3QgdW5oZWFsdGh5IG9ic2Vzc2lvbiB3aXRoIHRyaWFuZ2xlcy4gQmVjYXVzZSBvZiBoaXMgZGlzY3JldGUgbmF0dXJlLCBTaW1vbiYjMzk7cyBmYXZvcml0ZSBraW5kIG9mIHRyaWFuZ2xlcyBhcmUgdGhlIFB5dGhhZ29yZWFuIG9uZXMsIGluIHdoaWNoIHRoZSBzaWRlIGxlbmd0aHMgYXJlIHRocmVlIHBvc2l0aXZlIGludGVnZXJzIGEsIGIsIGFuZCBjIHN1Y2ggdGhhdCBhICZsZTsgYiBhbmQgYTxzdXA+MjxcL3N1cD4rYjxzdXA+MjxcL3N1cD4mbmJzcDs9IGM8c3VwPjI8XC9zdXA+LjxcL3A+XHJcblxyXG48cD5SZWNlbnRseSwgU2ltb24gaGFzIGRpc2NvdmVyZWQgdGhlIGZhbnRhc3RpYyB3b3JsZCBvZiBjb3VudGluZyBtb2R1bG8gc29tZSBpbnRlZ2VyIG4uIEFzIHlvdSBtYXkgaW1hZ2luZSwgaGUgcXVpY2tseSByZWFsaXplcyB0aGF0IHRoZXJlIGFyZSBtdWx0aXR1ZGVzIG9mIFB5dGhhZ29yZWFuIHRyaXBsZXMgdG8gd2hpY2ggaGUgaGFzIHByZXZpb3VzbHkgYmVlbiBvYmxpdmlvdXMhIFNpbW9uIHRoZXJlZm9yZSBzZXRzIG91dCB0byBmaW5kIGFsbCBQeXRoYWdvcmVhbiB0cmlwbGVzIG1vZHVsbyBuLCBpLmUuLCBhbGwgdHJpcGxlcyBvZiBpbnRlZ2VycyBhLCBiIGFuZCBjIGJldHdlZW4gMSBhbmQgbiAtIDEgc3VjaCB0aGF0IGEgJmxlOyBiIGFuZCBhPHN1cD4yPFwvc3VwPitiPHN1cD4yPFwvc3VwPiZuYnNwOyZlcXVpdjsgYzxzdXA+MjxcL3N1cD4mbmJzcDsobW9kIG4pLjxcL3A+XHJcblxyXG48cD5BcyBTaW1vbiYjMzk7cyBiZXN0IGZyaWVuZCwgeW91IHJlYWxpemUgdGhhdCB0aGVyZSBpcyBub3QgbXVjaCBob3BlIGluIGRldGVycmluZyBTaW1vbiBmcm9tIGhpcyBjcmF6eSBwbGFucywgc28geW91IGRlY2lkZSB0byBoZWxwIGhpbSBieSBjb21wdXRpbmcgaG93IG1hbnkgc3VjaCB0cmlwbGVzIHRoZXJlIGFyZSwgc28gdGhhdCBTaW1vbiB3aWxsIGtub3cgd2hlbiBoaXMgd29yayBpcyBkb25lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGludGVnZXIgbiwgc2F0aXNmeWluZyAyICZsZTsgbiAmbGU7IDUwMCZuYnNwOzAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBQeXRoYWdvcmVhbiB0cmlwbGVzIG1vZHVsbyBuLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=