#include <bits/stdc++.h>
using namespace std;
long long n, k;
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%lld%lld", &n, &k);
    long long ans = 0;
    for (ans = 0; n / k;) {
      ans++;
      ans += n % k;
      n /= k;
    }
    ans += n;
    printf("%lld\n", ans);
  }
}
