시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 47 6 4 22.222%

문제

체스에서 나이트는 가로로 두 칸, 세로로 한 칸 이동하거, 가로로 한 칸, 세로로 두 칸 이동할 수 있다.

크기가 무한대인 체스판 (0, 0) 위에 나이트가 하나 놓여져 있다면, 나이트는 (1,2), (-1,2), (1,-2), (-1,-2), (2,1), (-2,1), (2,-1), (-2,-1)로 이동할 수 있다.

두 정수 x와 y가 주어졌을 때, 크기가 무한대인 체스판의 (0, 0)에서 (x, y)까지 최소 몇 번 만에 이동할 수 있는지 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 두 정수 x와 y가 주어진다. 두 값의 절대값은 십억을 넘지 않는다.

입력의 마지막 줄에는 END가 주어진다.

출력

각 테스트 케이스마다, 나이트가 (0, 0)에서 (x, y)로 이동하려면 최소 몇 번이 필요한지 출력한다.

예제 입력 1

1 2
2 4
END

예제 출력 1

1
2
W3sicHJvYmxlbV9pZCI6IjQxNjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWM3NzRcdWQyYjhcdWM3NTggXHVjNWVjXHVkNTg5IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NoZXNzKDEpLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyODFweDsgd2lkdGg6MjgzcHhcIiBcLz5cdWNjYjRcdWMyYTRcdWM1ZDBcdWMxMWMgXHViMDk4XHVjNzc0XHVkMmI4XHViMjk0IFx1YWMwMFx1Yjg1Y1x1Yjg1YyBcdWI0NTAgXHVjZTc4LCBcdWMxMzhcdWI4NWNcdWI4NWMgXHVkNTVjIFx1Y2U3OCBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjNzAsIFx1YWMwMFx1Yjg1Y1x1Yjg1YyBcdWQ1NWMgXHVjZTc4LCBcdWMxMzhcdWI4NWNcdWI4NWMgXHViNDUwIFx1Y2U3OCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMDZjXHVhZTMwXHVhYzAwIFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3OCBcdWNjYjRcdWMyYTRcdWQzMTAgKDAsIDApIFx1YzcwNFx1YzVkMCBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVkNTU4XHViMDk4IFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YjI5NCAoMSwyKSwgKC0xLDIpLCAoMSwtMiksICgtMSwtMiksICgyLDEpLCAoLTIsMSksICgyLC0xKSwgKC0yLC0xKVx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzgxNVx1YzIxOCB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMDZjXHVhZTMwXHVhYzAwIFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3OCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggKDAsIDApXHVjNWQwXHVjMTFjICh4LCB5KVx1YWU0Y1x1YzljMCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViNDUwIFx1YzgxNVx1YzIxOCB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVhYzEyXHVjNzU4IFx1YzgwOFx1YjMwMFx1YWMxMlx1Yzc0MCBcdWMyZWRcdWM1YjVcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgRU5EXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwICgwLCAwKVx1YzVkMFx1YzExYyAoeCwgeSlcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViODI0XHViYTc0IFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHViYzg4XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDE2MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktuaWdodCdzIFRyaXAiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hlc3MoMSkucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjI4MXB4OyB3aWR0aDoyODNweFwiIFwvPkluIGNoZXNzLCBlYWNoIG1vdmUgb2YgYSBrbmlnaHQgY29uc2lzdHMgb2YgbW92aW5nIGJ5IHR3byBzcXVhcmVzIGhvcml6b250YWxseSBhbmQgb25lIHNxdWFyZSB2ZXJ0aWNhbGx5LCBvciBieSBvbmUgc3F1YXJlIGhvcml6b250YWxseSBhbmQgdHdvIHNxdWFyZXMgdmVydGljYWxseS4gQSBrbmlnaHQgbWFraW5nIG9uZSBtb3ZlIGZyb20gbG9jYXRpb24gKDAsMCkgb2YgYW4gaW5maW5pdGUgY2hlc3MgYm9hcmQgd291bGQgZW5kIHVwIGF0IG9uZSBvZiB0aGUgZm9sbG93aW5nIGVpZ2h0IGxvY2F0aW9uczogKDEsMiksICgtMSwyKSwgKDEsLTIpLCAoLTEsLTIpLCAoMiwxKSwgKC0yLDEpLCAoMiwtMSksICgtMiwtMSkuPFwvcD5cclxuXHJcbjxwPlN0YXJ0aW5nIGZyb20gbG9jYXRpb24gKDAsMCksIHdoYXQgaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIHJlcXVpcmVkIGZvciBhIGtuaWdodCB0byBnZXQgdG8gc29tZSBvdGhlciBhcmJpdHJhcnkgbG9jYXRpb24gKHgseSk/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIHggYW5kIHksIGVhY2ggd2l0aCBhYnNvbHV0ZSB2YWx1ZSBhdCBtb3N0IG9uZSBiaWxsaW9uLiBUaGUgaW50ZWdlcnMgZGVzaWduYXRlIGEgbG9jYXRpb24gKHgseSkgb24gdGhlIGluZmluaXRlIGNoZXNzIGJvYXJkLiBUaGUgZmluYWwgbGluZSBjb250YWlucyB0aGUgd29yZCBFTkQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGxvY2F0aW9uIGluIHRoZSBpbnB1dCwgb3V0cHV0IGEgbGluZSBjb250YWluaW5nIG9uZSBpbnRlZ2VyLCB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMgcmVxdWlyZWQgZm9yIGEga25pZ2h0IHRvIG1vdmUgZnJvbSAoMCwwKSB0byAoeCwgeSkuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==