问题 CS: Digit sum

函数S_b(n)是b进制的n所有数位之和。

如S₁₀(233)=2＋3＋3=8,S₂(8)=1＋0＋0=1,S₂(7)=1＋1＋1=3。
给定N和b，你需要计算 $\sum_{n=1}^{N} S_b(n)$

输入的第一行给出了测试案例的数量，T。
接下来是T个测试用例。每个测试用例以包含一行.两个整数N和b。

$1 \leq T \leq 100000$
$1 \leq N \leq 10^6$
$2 \leq b \leq 10$

对于每个测试案例，输出一行，格式如 Case #x: y，其中x是测试案例编号（从1开始），y是答案。

2
10 10
8 2

Case #1: 46
Case #2: 13