#include <bits/stdc++.h>
using namespace std;
int main() {
  int no;
  cin >> no;
  long long int n[no], k[no], sol[no];
  for (int i = 0; i < no; i++) cin >> n[i] >> k[i];
  for (int i = 0; i < no; i++) sol[i] = 0;
  for (int i = 0; i < no; i++) {
    if (n[i] < k[i])
      sol[i] = n[i];
    else {
      while (n[i] != 0) {
        if (n[i] % k[i] == 0) {
          n[i] = n[i] / k[i];
          sol[i]++;
        } else {
          sol[i] = sol[i] + (n[i] % k[i]);
          n[i] = n[i] - (n[i] % k[i]);
        }
      }
    }
  }
  for (int i = 0; i < no; i++) cout << sol[i] << "\n";
}
