已知整数n和整数k。
在一次操作中，你可以执行以下两种变换中的任意一个:
（1）将n减少1，即n=n-1;
（2）如果n能被k整除，则用n除以k，即n=n/k
例如，如果n=27, k=3，您可以执行以下步骤:27→26→25→24→8→7→6→2→1→0。
请问，从n变换到0的最少操作次数是多少？已知整数n和整数k。
在一次操作中，你可以执行以下两种变换中的任意一个:
（1）将n减少1，即n=n-1;
（2）如果n能被k整除，则用n除以k，即n=n/k
例如，如果n=27, k=3，您可以执行以下步骤:27→26→25→24→8→7→6→2→1→0。
请问，从n变换到0的最少操作次数是多少？第一行一个整数t (1≤t≤100)：测试用例数；
接下来共t行，每个测试用例一行，共两个整数n和k (1≤n≤1018, 2≤k≤1018)。共t行，每个测试用例输出一行一个整数，将n变换到0的最少操作次数。
2 59 3 1000000000000000000 10
8 19