题目描述

给定一个整数 $n$ 和一个整数 $k$。

每一步你可以进行以下两种操作之一：

• 将 $n$ 减 $1$；
• 如果 $n$ 能被 $k$ 整除，则将 $n$ 除以 $k$。

例如，如果 $n = 27$ 且 $k = 3$，你可以按如下步骤操作：$27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$。

请你计算从 $n$ 变到 $0$ 所需的最少步数。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 100$），表示询问的组数。

每组询问包含一行，包含两个整数 $n$ 和 $k$（$1 \le n \le 10^{18}$，$2 \le k \le 10^{18}$）。

输出格式

对于每组询问，输出一行一个整数，表示从 $n$ 变到 $0$ 所需的最少步数。

说明/提示

第一组样例的操作步骤为：$59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$。

第二组样例中，你需要将 $n$ 除以 $k$ 共 $18$ 次，然后再将 $n$ 减 $1$。

由 ChatGPT 4.1 翻译

样例

2
59 3
1000000000000000000 10

8
19