#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int tc;
long long n, k;
int main() {
  cin >> tc;
  while (tc--) {
    cin >> n >> k;
    long long ans = 0;
    while (n) {
      if (n % k == 0)
        n /= k;
      else
        n--;
      long long x = n / k * k;
      ans += (n - x);
      n = x;
      ans++;
    }
    cout << ans << endl;
  }
  return 0;
}
