You are given an integer n and an integer k.

In one step you can do one of the following moves: 

  * decrease n by 1; 
  * divide n by k if n is divisible by k. 



For example, if n = 27 and k = 3 you can do the following steps: 27 → 26 → 25 → 24 → 8 → 7 → 6 → 2 → 1 → 0.

You are asked to calculate the minimum number of steps to reach 0 from n. 

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of queries.

The only line of each query contains two integers n and k (1 ≤ n ≤ 10^{18}, 2 ≤ k ≤ 10^{18}).

Output

For each query print the minimum number of steps to reach 0 from n in single line. 

Example

Input


2
59 3
1000000000000000000 10


Output


8
19

Note

Steps for the first test case are: 59 → 58 → 57 → 19 → 18 → 6 → 2 → 1 → 0.

In the second test case you have to divide n by k 18 times and then decrease n by 1.
#include <bits/stdc++.h>
using namespace std;
long long int spf[1000001];
void sieve1() {
  spf[1] = 1;
  for (int i = 2; i < 1000001; i++) spf[i] = i;
  for (int i = 4; i < 1000001; i += 2) spf[i] = 2;
  for (int i = 3; i * i < 1000001; i++) {
    if (spf[i] == i) {
      for (int j = i * i; j < 1000001; j += i)
        if (spf[j] == j) spf[j] = i;
    }
  }
}
long long int getFactorization(int x) {
  vector<int> ret;
  long long int p = 0;
  while (x != 1) {
    ret.push_back(spf[x]);
    x = x / spf[x];
  }
  sort(ret.begin(), ret.end());
  for (int i = 0; i < ret.size() - 1; i++) {
    if (ret[i] != ret[i + 1]) p = p + ret[i];
  }
  p = p + ret[ret.size() - 1];
  return p;
}
long long int d[1000055], u = 0;
void Sieve(int n) {
  bool prime[n + 1];
  memset(prime, true, sizeof(prime));
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (int i = p * 2; i <= n; i += p) prime[i] = false;
    }
  }
  for (int p = 2; p <= n; p++)
    if (prime[p]) {
      d[u] = p;
      u++;
    }
}
long long int minverse(long long int x, long long int n, long long int M) {
  if (n == 0)
    return 1;
  else if (n % 2 == 0)
    return minverse((x * x) % M, n / 2, M);
  else
    return (x * minverse((x * x) % M, (n - 1) / 2, M)) % M;
}
long long int prime(long long int n) {
  long long int i;
  if (n == 1 || n == 0) return 0;
  for (i = 2; i < sqrt(n); i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    long long int n, k, ans = 0;
    cin >> n >> k;
    if (k == 1)
      ans = n;
    else {
      long long int p;
      while (n > 0) {
        p = (n - (n / k) * k);
        n = n - p;
        ans += p;
        if (n > 0) {
          ans++;
        }
        n = n / k;
      }
    }
    cout << ans << endl;
  }
  return 0;
}
