#include <bits/stdc++.h>
using namespace std;
int main() {
  long long tst, n, a, one, two, res;
  cin >> tst;
  while (tst--) {
    cin >> n >> a;
    one = two = res = 0;
    while (n) {
      if (n / a > 0)
        res += n % a + 1;
      else
        res += n % a;
      n = n / a;
    }
    cout << res << endl;
  }
  return 0;
}
