#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long v = 0, c = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') c = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    v = v * 10 + ch - 48;
    ch = getchar();
  }
  return v * c;
}
int main() {
  int T = read();
  while (T--) {
    long long n = read(), k = read();
    long long ans = 0;
    while (n) {
      ans += (n % k);
      n -= n % k;
      if (n == 0) break;
      ans++;
      n = n / k;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
