{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eA digit sum $S_b(n)$ is a sum of the base-$b$ digits of $n$. Such as $S_{10}(233) \u003d 2 + 3 + 3 \u003d 8$, $S_{2}(8)\u003d1 + 0 + 0 \u003d 1$, $S_{2}(7)\u003d1 + 1 + 1 \u003d 3$.\u003c/p\u003e\n\u003cp\u003eGiven $N$ and $b$, you need to calculate $\\sum_{n\u003d1}^{N} S_b(n)$.\u003c/p\u003e\n\u003ch3\u003eInputFile\u003c/h3\u003e\n\u003cp\u003eThe first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing two integers $N$ and $b$.\u003c/p\u003e\n\u003cp\u003e$1 \\leq T \\leq 100000$\u003c/p\u003e\n\u003cp\u003e$1 \\leq N \\leq 10^6$\u003c/p\u003e\n\u003cp\u003e$2 \\leq b \\leq 10$\u003c/p\u003e\n\u003ch3\u003eOutputFile\u003c/h3\u003e\n\u003cp\u003eFor each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is answer.\u003c/p\u003e"}},{"title":"Sample 1","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\u003e2\n10 10\n8 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 46\nCase #2: 13\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}