← 返回题目列表

Codeforces · 1175/A

A. 从英雄到零

中文机器翻译题面 查看原题

给你一个整数 $$$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$$$ 的最小步骤数。

示例

输入 #1

2
59 3
1000000000000000000 10

输出 #1

8
19

注意

第一个测试用例的步骤是:$$$59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$。

在第二个测试用例中,您必须将 $$$n$$$ 除以 $$$k$$$ $$$18$$$ 次,然后将 $$$n$$$ 减去 $$$1$$$。