#include <bits/stdc++.h>
using namespace std;
long long func(long long x, long long y);
int main() {
  long long a, b;
  long long i, j, t, q, c;
  cin >> t;
  vector<long long> n;
  vector<long long> k;
  vector<long long> v;
  n.reserve(t);
  k.reserve(t);
  v.reserve(t);
  for (q = 0; q < t; q = q + 1) {
    cin >> a >> b;
    n.push_back(a);
    k.push_back(b);
  }
  for (q = 0; q < t; q = q + 1) {
    c = func(n[q], k[q]);
    v.push_back(c);
  }
  for (i = 0; i < t; i = i + 1) {
    cout << v[i] << " ";
  }
}
long long func(long long x, long long y) {
  long long i, j;
  if (x < y) {
    return (x);
  }
  for (i = 0; x != 0;) {
    j = x % y;
    if (j == 0) {
      x = x / y;
      i = i + 1;
    } else {
      x = x - j;
      i = i + j;
    }
  }
  return (i);
}
