#include <bits/stdc++.h>
using namespace std;
const long long md = 1e9 + 7;
long long a[1000005], n;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T;
  for (cin >> T; T--;) {
    long long q, m, k, h, ans = 0, sum = 0, p, x, y;
    cin >> n >> k;
    while (n) {
      if (n % k) {
        ans += n % k;
        n -= n % k;
      } else {
        ans++;
        n /= k;
      }
    }
    cout << ans << '\n';
  }
}
