시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 276 81 70 37.433%

문제

선영이는 당구대를 상근이에게 빌렸다. 상근이는 선영이에게 공 16개가 들어갈 수 있는 4×4 크기의 트레이도 같이 주었다. 이 트레이는 그림 (a)와 같이 생겼다. 흰색 공은 큐 볼이고, 나머지 15개 공은 1부터 15까지 숫자가 적혀져 있다.

포켓볼을 시작하기 전에 숫자가 적혀져 있는 공은 삼각형 모양으로 빠짐없이 배치해야 한다. 이 배치는 그림 b에 나와있다.

선영이는 포켓볼과 비슷하지만, 큐 볼과 숫자가 적혀져 있는 x개 공을 가지고 하는 새로운 게임을 하나 창안했다. 이때, 공 x개를 삼각형 모양으로, x+1개를 m×m크기의 트레이에 넣을 수 있어야 한다. a와 b가 주어졌을 때, a보다 크고 b보다 작은 x+1 중에서 선영이가 만든 게임을 즐길 수 있는 x+1의 개수를 구하는 프로그램을 작성하시오. 공을 삼각형 모양을 만들고 ,트레이에 넣을 때, 모든 공을 사용해야 하고, 빈 칸 (삼각형, 사각형을 이루지 못하는 칸) 이 있으면 안된다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, a와 b가 주어진다. (0 < a < b ≤ 109)

입력의 마지막 줄에는 0 0이 주어진다.

출력

각 테스트 케이스에 대해서, 다음을 출력한다.

case n: k

k는 a < x+1 < b인 x중에서 공 x개를 삼각형 모양으로 만들 수 있고, x+1개를 정사각형 트레이에 넣을 수 있는 x의 개수이다.

예제 입력 1

15 17
14 16
1 20
0 0

예제 출력 1

Case 1: 1
Case 2: 0
Case 3: 2
W3sicHJvYmxlbV9pZCI6IjQwMzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZWNcdWNmMTNcdWJjZmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIyZjlcdWFkNmNcdWIzMDBcdWI5N2MgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YmU0Y1x1YjgzOFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWFjZjUgMTZcdWFjMWNcdWFjMDAgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgNCZ0aW1lczs0IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQyYjhcdWI4MDhcdWM3NzRcdWIzYzQgXHVhYzE5XHVjNzc0IFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVjNzc0IFx1ZDJiOFx1YjgwOFx1Yzc3NFx1YjI5NCBcdWFkZjhcdWI5YmMgKGEpXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFjYmNcdWIyZTQuIFx1ZDc3MFx1YzBjOSBcdWFjZjVcdWM3NDAgXHVkMDUwIFx1YmNmY1x1Yzc3NFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIDE1XHVhYzFjIFx1YWNmNVx1Yzc0MCAxXHViZDgwXHVkMTMwIDE1XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQzZWNcdWNmMTNcdWJjZmNcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjODAxXHVkNjAwXHVjODM4IFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWM3NDAgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWJlNjBcdWM5ZDBcdWM1YzZcdWM3NzQgXHViYzMwXHVjZTU4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YmMzMFx1Y2U1OFx1YjI5NCBcdWFkZjhcdWI5YmMgYlx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcG9ja2V0YmFsbC5wbmdcIiBzdHlsZT1cImhlaWdodDoxOTlweDsgd2lkdGg6NDAzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1ZDNlY1x1Y2YxM1x1YmNmY1x1YWNmYyBcdWJlNDRcdWMyYjdcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1ZDA1MCBcdWJjZmNcdWFjZmMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyOTQgeFx1YWMxYyBcdWFjZjVcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNjM2RcdWM1NDhcdWQ1ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhY2Y1IHhcdWFjMWNcdWI5N2MgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YywgeCsxXHVhYzFjXHViOTdjIG0mdGltZXM7bVx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQyYjhcdWI4MDhcdWM3NzRcdWM1ZDAgXHViMTIzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBhXHVjNjQwIGJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgYVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjZTAgYlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgeCsxIFx1YzkxMVx1YzVkMFx1YzExYyBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5OTBcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCB4KzFcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjZjVcdWM3NDQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFjZTAgLFx1ZDJiOFx1YjgwOFx1Yzc3NFx1YzVkMCBcdWIxMjNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVhY2Y1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YmU0OCBcdWNlNzggKFx1YzBiY1x1YWMwMVx1ZDYxNSwgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVjZTc4KSBcdWM3NzQgXHVjNzg4XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBhXHVjNjQwIGJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbHQ7IGEgJmx0OyBiICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwIDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViMmU0XHVjNzRjXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuY2FzZSBuOiBrPFwvcHJlPlxyXG5cclxuPHA+a1x1YjI5NCBhICZsdDsgeCsxICZsdDsgYlx1Yzc3OCB4XHVjOTExXHVjNWQwXHVjMTFjIFx1YWNmNSB4XHVhYzFjXHViOTdjIFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWFjZTAsIHgrMVx1YWMxY1x1Yjk3YyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMmI4XHViODA4XHVjNzc0XHVjNWQwIFx1YjEyM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IHhcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQwMzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFdmVyeW9uZSBvdXQgb2YgdGhlIFBvb2wiLCJkZXNjcmlwdGlvbiI6IjxwPldoZW4geW91IHJlbnQgYSB0YWJsZSBhdCBhIHBvb2wgaGFsbCwgdGhlIHByb3ByaWV0b3IgZ2l2ZXMgeW91IGEgNC1ieS00IHRyYXkgb2YgMTYgYmFsbHMsIGFzIHNob3duIGluIEZpZ3VyZSAoYSkgYmVsb3cuIE9uZSBvZiB0aGVzZSBiYWxscywgY2FsbGVkIHRoZSAmcXVvdDtjdWUgYmFsbCZxdW90OywgaXMgd2hpdGUsIGFuZCB0aGUgcmVtYWluaW5nIDE1IGFyZSBudW1iZXJlZCAxIHRocm91Z2ggMTUuIEF0IHRoZSBiZWdpbm5pbmcgb2YgYSBnYW1lLCB0aGUgbnVtYmVyZWQgYmFsbHMgYXJlIHJhY2tlZCB1cCBpbiBhIHRyaWFuZ2xlICh3aXRob3V0IHRoZSBjdWUgYmFsbCksIGFzIHNob3duIGluIEZpZ3VyZSAoYikuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcG9ja2V0YmFsbC5wbmdcIiBzdHlsZT1cImhlaWdodDoxOTlweDsgd2lkdGg6NDAzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Tm93IGltYWdpbmUgb3RoZXIgcG9vbC1saWtlIGdhbWVzIHdoZXJlIHlvdSBoYXZlIGEgY3VlIGJhbGwgYW5kIHggbnVtYmVyZWQgYmFsbHMuIFlvdSYjMzk7ZCBsaWtlIHRvIGJlIGFibGUgdG8gcmFjayB1cCB0aGUgeCBudW1iZXJlZCBiYWxscyBpbiBhIHRyaWFuZ2xlLCBhbmQgaGF2ZSBhbGwgeCArIDEgYmFsbHMgcGVyZmVjdGx5IGZpbGwgYSBzcXVhcmUgbS1ieS1tIHRyYXkuIEZvciB3aGF0IHZhbHVlcyBvZiB4IGlzIHRoaXMgcG9zc2libGU/IEluIHRoaXMgcHJvYmxlbSB5b3UmIzM5O2xsIGJlIGdpdmVuIGFuIGxvd2VyIGJvdW5kIGEgYW5kIHVwcGVyIGJvdW5kIGIsIGFuZCBhc2tlZCBob3cgbWFueSBudW1iZXJzIHdpdGhpbiB0aGlzIHJhbmdlIGhhdmUgdGhlIGFib3ZlIHByb3BlcnR5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgZm9yIGVhY2ggdGVzdCBjYXNlIHdpbGwgb25lIGxpbmUgY29udGFpbmluIHR3byBpbnRlZ2VycyBhIGIsIHdoZXJlIDAgJmx0OyBhICZsdDsgYiAmbGU7IDEwPHN1cD45PFwvc3VwPi4gVGhlIGxpbmUgMCAwIHdpbGwgZm9sbG93IHRoZSBsYXN0IHRlc3QgY2FzZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb25lIGxpbmUgb2Ygb3V0cHV0IGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxwcmU+Q2FzZSBuOiBrPFwvcHJlPlxyXG5cclxuPHA+aWYgdGhlcmUgYXJlIGsgaW50ZWdlcnMgeCBzdWNoIHRoYXQgYSAmbHQ7IHggKyAxICZsdDsgYiwgeCBiYWxscyBjYW4gYmUgcmFja2VkIHVwIGluIGEgdHJpYW5nbGUsIGFuZCB4ICsgMSBiYWxscyBmaSBsbCBhIHNxdWFyZSB0cmF5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==