#include <bits/stdc++.h>
using namespace std;
bool p(long long n) {
  for (int i = 2; i <= sqrt(n); i++)
    if (n % i == 0) return 0;
  return 1;
}
int main() {
  int t;
  cin >> t;
  for (int T = 1; T <= t; T++) {
    long long n, k, c = 0;
    cin >> n >> k;
    while (n) {
      if (n == 0) break;
      if (n % k == 0)
        c++, n /= k;
      else {
        long long a = n / k;
        long long b = a * k;
        if (a != 0)
          c += (n - b);
        else
          c += n;
        n = b;
      }
    }
    cout << c << endl;
  }
}
