题目描述

给定一个十进制数 $N$，将它转换成 $K$ 进制后，计算所有数码之和。

例如 $N = 100$，$K = 16$，$100$ 的十六进制是 $64$，数码 $6$ 和 $4$ 之和为 $10$。

注意：数码 $A\sim F$ 分别表示 $10\sim15$。

输入格式

一行两个整数 $N, K$。

输出格式

一个整数，表示 $N$ 在 $K$ 进制下各位数码之和。

样例输入

100 16

样例输出

10

样例输入 2

30 2

样例输出 2

4

提示

$255$ 的十六进制是 $FF$，$F$ 代表数码 $15$，各位数码之和为 $15+15=30$。

$0 \le N \le 10^9$，$2 \le K \le 16$。