{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Dr. Mob has just discovered a Deathly Bacteria. He named it RC-01. RC-01 has a very strange reproduction system. RC-01 lives exactly **x** days. Now RC-01 produces exactly **p** new deadly Bacteria where **x \u003d b\u003csup\u003ep\u003c/sup\u003e** (where **b, p** are integers). More generally, **x** is a perfect **p\u003csup\u003eth\u003c/sup\u003e** power. Given the lifetime **x** of a mother RC-01 you are to determine the maximum number of new RC-01 which can be produced by the mother RC-01."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 50)**, denoting the number of test cases.\n\nEach case starts with a line containing an integer **x**. You can assume that **x** will have magnitude at least 2 and be within the range of a 32 bit signed integer."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the largest integer **p** such that **x** is a perfect **p\u003csup\u003eth\u003c/sup\u003e** power."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e3\n17\n1073741824\n25\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 1\nCase 2: 30\nCase 3: 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}