시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 183 59 41 28.472%

문제

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

직각삼각형은 세 변의 길이가 양의 정수 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
W3sicHJvYmxlbV9pZCI6IjUwNTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWQwYzBcdWFjZTBcdWI3N2NcdWMyYTRcdWM3NTggXHVjODE1XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YzljMFx1YjA5OFx1Y2U2MCBcdWM4MTVcdWIzYzRcdWI4NWMgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBcdWMwYmNcdWFjMDFcdWQ2MTUgXHVjOTExXHVjNWQwXHVjMTFjXHViM2M0IFx1YzljMVx1YWMwMVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjOWMxXHVhYzAxXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YzEzOCBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggYSwgYiwgY1x1Yzc3YyBcdWI1NGMsIGEgJmxlOyBiXHVjNjQwIGE8c3VwPjI8XC9zdXA+K2I8c3VwPjI8XC9zdXA+ID0gYzxzdXA+MjxcL3N1cD5cdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5ZDBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG48cD5cdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWMgXHViMDk4XHViYTM4XHVjOWMwIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWJjMzBcdWM2YjQgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzljMVx1YWMwMVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWMxMzggXHViY2MwXHVjNzU4IFx1YWQwMFx1YWNjNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVkNTNjXHVkMGMwXHVhY2UwXHViNzdjXHVjMmE0XHVjNzU4IFx1YzgxNVx1YjlhY1x1YzVkMCBcdWIwOThcdWJhMzhcdWM5YzAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzgwMVx1YzZhOVx1ZDU3NFx1YmNmNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgbi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBhLCBiLCBjXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIGEgJmxlOyBiXHVjNjQwIGE8c3VwPjI8XC9zdXA+K2I8c3VwPjI8XC9zdXA+ICZlcXVpdjsgYzxzdXA+MjxcL3N1cD4gKG1vZCBuKSBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjMTM4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuXHJcbjxwPm5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMDk4XHViYTM4XHVjOWMwIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWM4MDFcdWM2YTlcdWQ1NWMgXHVkNTNjXHVkMGMwXHVhY2UwXHViNzdjXHVjMmE0XHVjNzU4IFx1YzgxNVx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgYSwgYiwgY1x1YWMwMCBcdWJhODcgXHVhYzFjIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgbiAmbGU7IDUwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IG5cdWM3M2NcdWI4NWMgXHViMDk4XHViYTM4XHVjOWMwIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWQ1M2NcdWQwYzBcdWFjZTBcdWI3N2NcdWMyYTRcdWM3NTggXHVjODE1XHViOWFjXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBhLCBiLCBjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTA1MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikp1c3QgQSBGZXcgTW9yZSBUcmlhbmdsZXMhIiwiZGVzY3JpcHRpb24iOiI8cD5TaW1vbiBIYXBsZXMgaXMgYSBzb21ld2hhdCBwZWN1bGlhciBwZXJzb24uIE5vdCBxdWl0ZSBoaXAsIG5vdCBxdWl0ZSBzcXVhcmUsIGhlIGlzIG1vcmUgb2YgYSB0cmlhbmd1bGFyIG5hdHVyZTogZXZlciBzaW5jZSBjaGlsZGhvb2QsIGhlIGhhcyBoYWQgYW4gYWxtb3N0IHVuaGVhbHRoeSBvYnNlc3Npb24gd2l0aCB0cmlhbmdsZXMuIEJlY2F1c2Ugb2YgaGlzIGRpc2NyZXRlIG5hdHVyZSwgU2ltb24mIzM5O3MgZmF2b3JpdGUga2luZCBvZiB0cmlhbmdsZXMgYXJlIHRoZSBQeXRoYWdvcmVhbiBvbmVzLCBpbiB3aGljaCB0aGUgc2lkZSBsZW5ndGhzIGFyZSB0aHJlZSBwb3NpdGl2ZSBpbnRlZ2VycyBhLCBiLCBhbmQgYyBzdWNoIHRoYXQgYSAmbGU7IGIgYW5kIGE8c3VwPjI8XC9zdXA+K2I8c3VwPjI8XC9zdXA+Jm5ic3A7PSBjPHN1cD4yPFwvc3VwPi48XC9wPlxyXG5cclxuPHA+UmVjZW50bHksIFNpbW9uIGhhcyBkaXNjb3ZlcmVkIHRoZSBmYW50YXN0aWMgd29ybGQgb2YgY291bnRpbmcgbW9kdWxvIHNvbWUgaW50ZWdlciBuLiBBcyB5b3UgbWF5IGltYWdpbmUsIGhlIHF1aWNrbHkgcmVhbGl6ZXMgdGhhdCB0aGVyZSBhcmUgbXVsdGl0dWRlcyBvZiBQeXRoYWdvcmVhbiB0cmlwbGVzIHRvIHdoaWNoIGhlIGhhcyBwcmV2aW91c2x5IGJlZW4gb2JsaXZpb3VzISBTaW1vbiB0aGVyZWZvcmUgc2V0cyBvdXQgdG8gZmluZCBhbGwgUHl0aGFnb3JlYW4gdHJpcGxlcyBtb2R1bG8gbiwgaS5lLiwgYWxsIHRyaXBsZXMgb2YgaW50ZWdlcnMgYSwgYiBhbmQgYyBiZXR3ZWVuIDEgYW5kIG4gLSAxIHN1Y2ggdGhhdCBhICZsZTsgYiBhbmQgYTxzdXA+MjxcL3N1cD4rYjxzdXA+MjxcL3N1cD4mbmJzcDsmZXF1aXY7IGM8c3VwPjI8XC9zdXA+Jm5ic3A7KG1vZCBuKS48XC9wPlxyXG5cclxuPHA+QXMgU2ltb24mIzM5O3MgYmVzdCBmcmllbmQsIHlvdSByZWFsaXplIHRoYXQgdGhlcmUgaXMgbm90IG11Y2ggaG9wZSBpbiBkZXRlcnJpbmcgU2ltb24gZnJvbSBoaXMgY3JhenkgcGxhbnMsIHNvIHlvdSBkZWNpZGUgdG8gaGVscCBoaW0gYnkgY29tcHV0aW5nIGhvdyBtYW55IHN1Y2ggdHJpcGxlcyB0aGVyZSBhcmUsIHNvIHRoYXQgU2ltb24gd2lsbCBrbm93IHdoZW4gaGlzIHdvcmsgaXMgZG9uZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIHNpbmdsZSBpbnRlZ2VyIG4sIHNhdGlzZnlpbmcgMiAmbGU7IG4gJmxlOyA1MDAmbmJzcDswMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2YgUHl0aGFnb3JlYW4gdHJpcGxlcyBtb2R1bG8gbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=