#include <bits/stdc++.h>
using namespace std;
long long n, a, b, c, d, m, z, p;
bool f = 0;
int main() {
  cin >> m;
  while (m--) {
    cin >> n >> a;
    while (n != 0) {
      if (n % a == 0) {
        n /= a;
        d++;
      } else {
        c = n % a;
        d += c;
        n -= c;
      }
    }
    cout << d << endl;
    d = 0;
  }
}
