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