시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 176 93 42 43.299%

문제

격자 정사각형은 모든 꼭짓점이 격자점 위에 있는 정사각형이다. 격자점은 x좌표와 y좌표가 모두 정수인 점이다. 예를 들어, (1,5)는 격자점이지만, (1, 1.5)는 아니다.

m×n 격자 위에 격자 정사각형은 총 몇 개가 있을까?

위의 그림은 4×4 격자 위에서 찾을 수 있는 격자 정사각형의 일부이다. 그림 1, 2, 3과 같이 축에 평행한 격자 정사각형도 있고, 4, 5, 6과 같이 평행하지 않은 정사각형도 있다. 그림 2, 4, 6의 정사각형은 넓이가 짝수이고, 1, 3, 5는 홀수이다.

격자의 크기가 주어졌을 때, 넓이가 홀수인 격자 정사각형은 총 몇 개가 있는지 구하는 프로그램을 작성하시오.

두 격자 정사각형이 네 변을 모두 공유하지 않으면 다른 정사각형이다.

입력

입력은 최대 50000줄로 이루어져 있다. 각 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100000) 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 입력마다 넓이가 홀수인 격자 정사각형의 수를 출력한다. 정답은 항상 64비트 정수(64-bit signed integer) 범위이다.

예제 입력 1

2 2
3 3
4 4
0 0

예제 출력 1

4
12
28
W3sicHJvYmxlbV9pZCI6Ijk2MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NDBcdWMyMTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjYTlcdWM3OTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NzQgXHVhY2E5XHVjNzkwXHVjODEwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LiBcdWFjYTlcdWM3OTBcdWM4MTBcdWM3NDAgeFx1Yzg4Y1x1ZDQ1Y1x1YzY0MCB5XHVjODhjXHVkNDVjXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NzggXHVjODEwXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoMSw1KVx1YjI5NCBcdWFjYTlcdWM3OTBcdWM4MTBcdWM3NzRcdWM5YzBcdWI5Y2MsICgxLCAxLjUpXHViMjk0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+bSZ0aW1lcztuIFx1YWNhOVx1Yzc5MCBcdWM3MDRcdWM1ZDAgXHVhY2E5XHVjNzkwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWNkMWQgXHViYTg3IFx1YWMxY1x1YWMwMCBcdWM3ODhcdWM3NDRcdWFlNGM/PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbGF0dGljZXNxdS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNzVweDsgd2lkdGg6NDM5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCA0JnRpbWVzOzQgXHVhY2E5XHVjNzkwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYTlcdWM3OTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViOWJjIDEsIDIsIDNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHVhY2E5XHVjNzkwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YjNjNCBcdWM3ODhcdWFjZTAsIDQsIDUsIDZcdWFjZmMgXHVhYzE5XHVjNzc0IFx1ZDNjOVx1ZDU4OVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWJjIDIsIDQsIDZcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YjExM1x1Yzc3NFx1YWMwMCBcdWM5ZGRcdWMyMThcdWM3NzRcdWFjZTAsIDEsIDMsIDVcdWIyOTQgXHVkNjQwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjYTlcdWM3OTBcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjExM1x1Yzc3NFx1YWMwMCBcdWQ2NDBcdWMyMThcdWM3NzggXHVhY2E5XHVjNzkwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWNkMWQgXHViYTg3IFx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWFjYTlcdWM3OTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YjEyNCBcdWJjYzBcdWM3NDQgXHViYWE4XHViNDUwIFx1YWNmNVx1YzcyMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViMmU0XHViOTc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWNkNWNcdWIzMDAgNTAwMDBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBtXHVhY2ZjIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG0sIG4gJmxlOyAxMDAwMDApIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1Yzc4NVx1YjgyNVx1YjljOFx1YjJlNCBcdWIxMTNcdWM3NzRcdWFjMDAgXHVkNjQwXHVjMjE4XHVjNzc4IFx1YWNhOVx1Yzc5MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzQwIFx1ZDU2ZFx1YzBjMSA2NFx1YmU0NFx1ZDJiOCBcdWM4MTVcdWMyMTgoNjQtYml0IHNpZ25lZCBpbnRlZ2VyKSBcdWJjOTRcdWM3MDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTYxNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvdW50aW5nIExhdHRpY2UgU3F1YXJlcyIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9sYXR0aWNlc3F1LnBuZ1wiIHN0eWxlPVwiZmxvYXQ6bGVmdDsgaGVpZ2h0OjI3NXB4OyB3aWR0aDo0MzlweFwiIFwvPkEgbGF0dGljZSBzcXVhcmUgaXMgYSBzcXVhcmUgd2hvc2UgdmVydGljZXMgYXJlIGFsbCBsYXR0aWNlIHBvaW50cy4gQSBsYXR0aWNlLXBvaW50IGlzIGEgcG9pbnQgaW4gQ2FydGVzaWFuIGNvb3JkaW5hdGUgc3lzdGVtIHdob3NlIGFic2Npc3NhIGFuZCBvcmRpbmF0ZSBhcmUgaW50ZWdlcnMuIEZvciBleGFtcGxlICgxLCA1KSBpcyBhIGxhdHRpY2UgcG9pbnQgYnV0ICgxLCAxLjUpIGlzIG5vdC4gSW4gYSAobiB4IG0pIGdyaWQgdGhlcmUgY2FuIGJlIG1hbnkgbGF0dGljZSBzcXVhcmVzLiBJbiB0aGUgZmlndXJlIG9uIHRoZSBsZWZ0IHlvdSBjYW4gc2VlIHNvbWUgbGF0dGljZSBzcXVhcmVzIGluIGEgKDR4NCkgZ3JpZC4gQ291bnRpbmcgbGF0dGljZSBzcXVhcmVzIHdpdGggYXhpcy1wYXJhbGxlbCBzaWRlcyAoRmlndXJlIDEsIEZpZ3VyZSAyIGFuZCBGaWd1cmUgMykgaXMgdHJpdmlhbCBidXQgdGhlcmUgYXJlIGxhdHRpY2Ugc3F1YXJlcyB3aG9zZSBzaWRlcyBhcmUgbm90IGF4aXMgcGFyYWxsZWwgKEZpZ3VyZSA0LCBGaWd1cmUgNSBhbmQgRmlndXJlIDYpIGFuZCBjb3VudGluZyB0aGVtIGlzIGp1c3QgYSBiaXQgaGFyZGVyLiBTb21lIG9mIHRoZXNlIHNxdWFyZXMgY2FuIGhhdmUgZXZlbiBhcmVhIChGaWd1cmUgMiwgRmlndXJlIDQsIEZpZ3VyZSA2KSBhbmQgc29tZSBvdGhlcnMgY2FuIGhhdmUgb2RkIGFyZWEgKEZpZ3VyZSAxLCBGaWd1cmUgMywgRmlndXJlIDUpLiBHaXZlbiBhbiAobSB4IG4pIGdyaWQgeW91ciBqb2IgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgY291bnRzIGhvdyBtYW55IGRpZmZlcmVudCBsYXR0aWNlIHNxdWFyZXMgd2l0aCBvZGQgYXJlYSBjYW4gYmUgZHJhd24gaW4gdGhhdCBncmlkLiBUd28gbGF0dGljZSBzcXVhcmVzIGFyZSBkaWZmZXJlbnQgaWYgdGhleSBkbyBub3Qgc2hhcmUgYWxsIGZvdXIgdmVydGljZXMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSBjb250YWlucyBhdCBtb3N0IDUwMDAwIGxpbmVzIG9mIGlucHV0cy4gRWFjaCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBtLCBuICgxICZsZTsgbSwgbiAmbGU7IDEwMDAwMCkuIElucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9lcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5hRm9yIGVhY2ggbGluZSBvZiBpbnB1dCBwcm9kdWNlIG9uZSBsaW5lIG9mIG91dHB1dC4gVGhpcyBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgUywgd2hpY2ggZGVub3RlcyBob3cgbWFueSBkaWZmZXJlbnQgbGF0dGljZSBzcXVhcmVzIHdpdGggb2RkIGFyZWEgY2FuIGJlIGRyYXduIGluIGFuIChtIHggbikgZ3JpZC4gWW91IGNhbiBhc3N1bWUgdGhhdCB0aGUgdmFsdWUgb2YgUyBmaXRzIGluIGEgNjQtYml0IHNpZ25lZCBpbnRlZ2VyLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==