{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003e\nFor a positive integer \u003cvar\u003ea\u003c/var\u003e, let \u003cvar\u003eS(a)\u003c/var\u003e be the sum of the digits in base \u003cvar\u003el\u003c/var\u003e.\nAlso let \u003cvar\u003eL(a)\u003c/var\u003e be the minimum \u003cvar\u003ek\u003c/var\u003e such that \u003cvar\u003eS^k(a)\u003c/var\u003e is less than or equal to \u003cvar\u003el-1\u003c/var\u003e.\nFind the minimum \u003cvar\u003ea\u003c/var\u003e such that \u003cvar\u003eL(a) \u003d N\u003c/var\u003e for a given \u003cvar\u003eN\u003c/var\u003e, and print \u003cvar\u003ea\u003c/var\u003e modulo \u003cvar\u003em\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nThe input contains several test cases, followed by a line containing \"0 0 0\".\nEach test case is given by a line with three integers \u003cvar\u003eN\u003c/var\u003e, \u003cvar\u003em\u003c/var\u003e, \u003cvar\u003el\u003c/var\u003e (\u003cvar\u003e0 \\leq N \\leq 10^5\u003c/var\u003e, \u003cvar\u003e1 \\leq m \\leq 10^9\u003c/var\u003e, \u003cvar\u003e2 \\leq l \\leq 10^9\u003c/var\u003e).\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nFor each test case, print its case number and the minimum \u003cvar\u003ea\u003c/var\u003e modulo \u003cvar\u003em\u003c/var\u003e as described above.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input\u003c/h2\u003e\n\n\u003cpre\u003e0 1000 10\n1 1000 10\n0 0 0\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input\u003c/h2\u003e\n\n\u003cpre\u003eCase 1: 1\nCase 2: 10\n\u003c/pre\u003e\n"}}]}