#include <bits/stdc++.h>   static const int INF = 0x3f3f3f3f;   static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;   static const long double epsilon = 1e-15;   static const long double pi = acos((long double)-1);   using namespace std;   inline void init_io() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);   }   const int MAX_N = 100001;   int arr[2 * MAX_N];   void rarr(int n) {     for (int(i) = (0); (i) < (n); i++) cin >> arr[i];   }   int main() {     init_io();     int t;     cin >> t;     while (t--) {       long long n, k;       cin >> n >> k;       long long ans = 0;       while (n) {         if (n % k) {           ans += n % k;           n = n - n % k;         } else {           ans++;           n /= k;         }       }       cout << ans <<   n ;     }     return 0;   }   