#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[]) {
  int cases;
  long long int n, k;
  cin >> cases;
  while (cases--) {
    long long int ans = 0;
    cin >> n >> k;
    while (n >= k) {
      ans += n % k + 1;
      n = n / k;
    }
    cout << ans + n << endl;
  }
  return 0;
}
