题目描述

给定一个正整数n，你可以对其进行如下两种操作：

1、减1操作：将n变为 n−1 消耗 1 点能量

2、整除操作：如果 n 能被 k 整除（k≥2），可以将 n 变为n/k消耗 0 点能量

请你计算将 n 变为 1 所需消耗的最少能量。

输入格式

第一行包含一个整数 T（1≤T≤100000），表示测试用例的数量。

接下来 T 行，每行两个整数 n 和 k，1≤n≤100000，2≤k≤100000）

输出格式

对于每个测试用例，输出一行一个整数，表示将 n 变为 1 所需的最少能量

3
10 2
10 3
1 2

1
1
0

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^7$。