暂无测试数据。

给出一个十进制数 $n$，求该数在 $k$ 进制下的数位和。比如 $n=10,k=3$ 时，$10_{(10)}=101_{{(3)}}$，数位和就是 $2$。

输入格式

第一行一个整数 $T\ (1\le T \le 100)$，表示测试数据的组数。

接下来 $T$ 行，每行两个整数 $n,k\ (1\le n \le 10^9, 2\le k \le 20)$。

输出格式

$T$ 行，每行一个整数表示答案。

3
10 3
233 10
233 20

2
8
24