#include <bits/stdc++.h>
using namespace std;
long long t, n, k, ans;
void read_input() {
  cin >> t;
  while (t--) {
    cin >> n >> k;
    while (n != 0) {
      if (n % k == 0) {
        n /= k;
        ans++;
      } else {
        ans += n % k;
        n -= n % k;
      }
    }
    cout << ans << endl;
    ans = 0;
  }
}
void solve() {}
void write_output() {}
int main() { read_input(); }
