#include <bits/stdc++.h>
using namespace std;
long long tmp[100];
int main() {
  int t;
  cin >> t;
  long long n[t];
  long long k[t];
  for (int i = 0; i < t; i++) {
    cin >> n[i] >> k[i];
  }
  long long rem = 0;
  for (int i = 0; i < t; i++) {
    for (long long j = 0; j < 1000000000000000000; j++) {
      if (n[i] % k[i] == 0) {
        n[i] = (n[i] / k[i]);
        tmp[i]++;
      }
      if (n[i] % k[i] != 0) {
        rem = n[i] % k[i];
        n[i] = n[i] - rem;
        tmp[i] += rem;
      }
      if (n[i] == 0) break;
    }
  }
  for (int i = 0; i < t; i++) {
    cout << tmp[i] << endl;
  }
}
