#include <bits/stdc++.h>
using namespace std;
int main() {
  long long t, n, k, steps, remainder;
  cin >> t;
  for (int l = 0; l < t; l++) {
    steps = 0;
    cin >> n >> k;
    if (k == 1) {
      cout << "1" << endl;
      continue;
    }
    while (n > 0) {
      remainder = n % k;
      if (remainder == 0) {
        steps++;
        n = n / k;
      } else {
        steps += remainder;
        n = n - remainder;
      }
    }
    cout << steps << endl;
  }
}
