{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cdiv style\u003d\"text-align: left; margin: 10px 0px;\"\u003e\u003cdiv style\u003d\"float: right; margin: 0px 0px 3px 10px;\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/e9cb30f42e98a30f0b2fd67d560f929b?v\u003d1715641314\" width\u003d\"250\"\u003e\u003c/div\u003e\u003cspan\u003e\r\n\u003cp\u003eBenjamin is going to host a party for his big promotion coming up.\u003c/p\u003e\r\n\u003cp\u003eEvery party needs candies, chocolates and beer, and of course Benjamin has prepared some of those. But as everyone likes to party, many more people showed up than he expected. The good news is that candies are enough. And for the beer, he only needs to buy some extra cups. The only problem is the chocolate.\u003c/p\u003e\r\n\u003cp\u003eAs Benjamin is only a \u0027small court officer\u0027 with poor salary even after his promotion, he can not afford to buy extra chocolate. So he decides to break the chocolate cubes into smaller pieces so that everyone can have some.\u003c/p\u003e\r\n\u003cp\u003eHe have two methods to break the chocolate. He can pick one piece of chocolate and break it into two pieces with bare hand, or put some pieces of chocolate together on the table and cut them with a knife at one time. You can assume that the knife is long enough to cut as many pieces of chocolate as he want.\u003c/p\u003e\r\n\u003cp\u003eThe party is coming really soon and breaking the chocolate is not an easy job. He wants to know what is the minimum number of steps to break the chocolate into unit-size pieces (cubes of size 1×1×1). He is not sure whether he can find a knife or not, so he wants to know the answer for both situations.\u003c/p\u003e\r\n\u003c/span\u003e\u003c/div\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line contains an integer \u003cb\u003eT\u003c/b\u003e (1 ≤ \u003cb\u003eT\u003c/b\u003e ≤ 10000), indicating the number of test cases.\u003c/p\u003e\r\n\r\n\u003cp\u003eEach test case contains one line with three integers \u003cb\u003eN\u003c/b\u003e, \u003cb\u003eM\u003c/b\u003e, \u003cb\u003eK\u003c/b\u003e (1 ≤ \u003cb\u003eN\u003c/b\u003e, \u003cb\u003eM\u003c/b\u003e, \u003cb\u003eK\u003c/b\u003e ≤ 2000), meaning the chocolate is a cube of size \u003cb\u003eN\u003c/b\u003e×\u003cb\u003eM\u003c/b\u003e×\u003cb\u003eK\u003c/b\u003e.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case in the input, print one line: \u003ctt\u003e\"Case #X: A B\"\u003c/tt\u003e, where \u003cb\u003eX\u003c/b\u003e is the test case number (starting with 1) , \u003cb\u003eA\u003c/b\u003e and \u003cb\u003eB\u003c/b\u003e are the minimum numbers of steps to break the chocolate into \u003cb\u003eN\u003c/b\u003e×\u003cb\u003eM\u003c/b\u003e×\u003cb\u003eK\u003c/b\u003e unit-size pieces with bare hands and knife respectively.\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1 1 3\r\n2 2 2\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 2 2\r\nCase #2: 7 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\n\u003c/div\u003e"}}]}