2019春 程序设计能力实训第一次机考

B. 数位和

单点时限: 2.0 sec

内存限制: 512 MB

“数位和”是指:把一个整数的各位累加后的结果。
例如正整数 $123456$ 的数位和是 $1+2+3+4+5+6=21$。
现在,请你帮忙计算一个整数 $n$ 在 $r$ 进制下的数位和,并用相应的进制输出结果。

输入格式

第 1 行:整数 $T (1\leq T\leq 10)$ 为问题数。

第 2 行:第一个问题的数据。包含两个正整数 $n (1\leq n\leq 2147483647)$ 和 $r (2\leq n\leq 16)$。

第 3 ∽ $T+1$ 行:后面问题的数据,格式与第一个问题相同。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等),然后在一行中输出用 $r$ 进制表示的十进制正整数 $n$ 转换成 $r$ 进制后的数位和。

样例

Input
2
123456 10
123456 2
Output
case #0:
21
case #1:
110

提示

当$r$进制大于10时,用大写字母A-F表示大于10的数字。

例如:十进制数29转换为16进制为 1D,此时数位和为14,则正确的输出应为:E