#include <bits/stdc++.h>
using namespace std;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    long long n, k;
    scanf("%lld %lld", &n, &k);
    long long ans = 0;
    while (n) {
      ans += n % k + 1;
      n = n - n % k;
      n = n / k;
    }
    printf("%lld\n", ans - 1);
  }
}
