#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  scanf("%d", &n);
  for (register int i = 0; i < n; ++i) {
    register long long a, b, cnt = 0;
    cin >> a >> b;
    while (a) {
      if (a % b) cnt += a % b;
      if (a < b) break;
      a /= b;
      cnt++;
    }
    cout << cnt << endl;
  }
}
