#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
inline void solve() {
  long long n, k;
  cin >> n >> k;
  long long ans = 0, val;
  while (n) {
    if (n % k) {
      val = n % k;
      n -= val;
      ans += val;
    } else
      n /= k, ans++;
  }
  cout << ans << endl;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) solve();
}
