#include <bits/stdc++.h>
using namespace std;
const long long int maxn = 1e3 + 2;
const long long int mod = 1e3 + 2;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n;
  long long int m, k;
  cin >> n;
  while (n--) {
    cin >> m >> k;
    long long int count = 0;
    while (m != 0) {
      if (m % k == 0) {
        m = m / k;
        count++;
      } else {
        long long int a = m % k;
        count += a;
        m = m - a;
      }
    }
    cout << count << endl;
  }
}
