#include <bits/stdc++.h>
using namespace std;
long long step = 0;
void dfs(long long n, long long k) {
  if (n == 0) return;
  long long c = n % k;
  if (c == 0) {
    step = step + 1;
    dfs(n / k, k);
  } else if (c <= k / 2) {
    step = step + c;
    dfs(n - c, k);
  } else {
    step = step + (k - c);
    dfs(n - k + c, k);
  }
}
int main() {
  int t;
  long long n, k;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    step = 0;
    dfs(n, k);
    printf("%lld\n", step);
  }
  return 0;
}
