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

문제

선영이는 당구대를 상근이에게 빌렸다. 상근이는 선영이에게 공 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+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1ZDNlY1x1Y2YxM1x1YmNmY1x1YWNmYyBcdWJlNDRcdWMyYjdcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1ZDA1MCBcdWJjZmNcdWFjZmMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyOTQgeFx1YWMxYyBcdWFjZjVcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNjM2RcdWM1NDhcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YWNmNSB4XHVhYzFjXHViOTdjIFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMsIHgrMVx1YWMxY1x1Yjk3YyBtJnRpbWVzO21cdWQwNmNcdWFlMzBcdWM3NTggXHVkMmI4XHViODA4XHVjNzc0XHVjNWQwIFx1YjEyM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gYVx1YzY0MCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIGFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhY2UwIGJcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIHgrMSBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YjljY1x1YjRlMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOTkwXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgeCsxXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVhY2Y1XHVjNzQ0IFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NDQgXHViOWNjXHViNGU0XHVhY2UwICxcdWQyYjhcdWI4MDhcdWM3NzRcdWM1ZDAgXHViMTIzXHVjNzQ0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1YWNmNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWJlNDggXHVjZTc4IChcdWMwYmNcdWFjMDFcdWQ2MTUsIFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM3NzRcdWI4ZThcdWM5YzAgXHViYWJiXHVkNTU4XHViMjk0IFx1Y2U3OCkgXHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgYVx1YzY0MCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmx0OyBhICZsdDsgYiAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YjJlNFx1Yzc0Y1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbmNhc2UgbjogazxcL3ByZT5cclxuXHJcbjxwPmtcdWIyOTQgYSAmbHQ7IHgrMSAmbHQ7IGJcdWM3NzggeFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjZjUgeFx1YWMxY1x1Yjk3YyBcdWMwYmNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVhY2UwLCB4KzFcdWFjMWNcdWI5N2MgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1ZDJiOFx1YjgwOFx1Yzc3NFx1YzVkMCBcdWIxMjNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCB4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MDMwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXZlcnlvbmUgb3V0IG9mIHRoZSBQb29sIiwiZGVzY3JpcHRpb24iOiI8cD5XaGVuIHlvdSByZW50IGEgdGFibGUgYXQgYSBwb29sIGhhbGwsIHRoZSBwcm9wcmlldG9yIGdpdmVzIHlvdSBhIDQtYnktNCB0cmF5IG9mIDE2IGJhbGxzLCBhcyBzaG93biBpbiBGaWd1cmUgKGEpIGJlbG93LiBPbmUgb2YgdGhlc2UgYmFsbHMsIGNhbGxlZCB0aGUgJnF1b3Q7Y3VlIGJhbGwmcXVvdDssIGlzIHdoaXRlLCBhbmQgdGhlIHJlbWFpbmluZyAxNSBhcmUgbnVtYmVyZWQgMSB0aHJvdWdoIDE1LiBBdCB0aGUgYmVnaW5uaW5nIG9mIGEgZ2FtZSwgdGhlIG51bWJlcmVkIGJhbGxzIGFyZSByYWNrZWQgdXAgaW4gYSB0cmlhbmdsZSAod2l0aG91dCB0aGUgY3VlIGJhbGwpLCBhcyBzaG93biBpbiBGaWd1cmUgKGIpLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BvY2tldGJhbGwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTk5cHg7IHdpZHRoOjQwM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk5vdyBpbWFnaW5lIG90aGVyIHBvb2wtbGlrZSBnYW1lcyB3aGVyZSB5b3UgaGF2ZSBhIGN1ZSBiYWxsIGFuZCB4IG51bWJlcmVkIGJhbGxzLiBZb3UmIzM5O2QgbGlrZSB0byBiZSBhYmxlIHRvIHJhY2sgdXAgdGhlIHggbnVtYmVyZWQgYmFsbHMgaW4gYSB0cmlhbmdsZSwgYW5kIGhhdmUgYWxsIHggKyAxIGJhbGxzIHBlcmZlY3RseSBmaWxsIGEgc3F1YXJlIG0tYnktbSB0cmF5LiBGb3Igd2hhdCB2YWx1ZXMgb2YgeCBpcyB0aGlzIHBvc3NpYmxlPyBJbiB0aGlzIHByb2JsZW0geW91JiMzOTtsbCBiZSBnaXZlbiBhbiBsb3dlciBib3VuZCBhIGFuZCB1cHBlciBib3VuZCBiLCBhbmQgYXNrZWQgaG93IG1hbnkgbnVtYmVycyB3aXRoaW4gdGhpcyByYW5nZSBoYXZlIHRoZSBhYm92ZSBwcm9wZXJ0eS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGZvciBlYWNoIHRlc3QgY2FzZSB3aWxsIG9uZSBsaW5lIGNvbnRhaW5pbiB0d28gaW50ZWdlcnMgYSBiLCB3aGVyZSAwICZsdDsgYSAmbHQ7IGIgJmxlOyAxMDxzdXA+OTxcL3N1cD4uIFRoZSBsaW5lIDAgMCB3aWxsIGZvbGxvdyB0aGUgbGFzdCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG9uZSBsaW5lIG9mIG91dHB1dCBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cHJlPkNhc2UgbjogazxcL3ByZT5cclxuXHJcbjxwPmlmIHRoZXJlIGFyZSBrIGludGVnZXJzIHggc3VjaCB0aGF0IGEgJmx0OyB4ICsgMSAmbHQ7IGIsIHggYmFsbHMgY2FuIGJlIHJhY2tlZCB1cCBpbiBhIHRyaWFuZ2xlLCBhbmQgeCArIDEgYmFsbHMgZmkgbGwgYSBzcXVhcmUgdHJheS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=