#include <bits/stdc++.h>
using namespace std;
#define int long long   // force all int → long long
int ilog_ceil(int a, int base) {
    int b = 0;
    int p = 1;
    while (p < a) {   // multiply until we reach or exceed a
        p *= base;
        b++;
    }
    return b;
}
// integer power function (fast exponentiation)
int ipow(int base, int exp) {
    int res = 1;
    while (exp > 0) {
        if (exp & 1) res *= base;
        base *= base;
        exp >>= 1;
    }
    return res;
}

// integer log: floor(log_base(n)), assumes base > 1
int ilog(int n, int base) {
    int ans = 0;
    while (n >= base) {
        n /= base;
        ans++;
    }
    return ans;
}

// integer ceil division: ceil(a / b), assumes b > 0
int iceil(int a, int b) {
    return (a + b - 1) / b;
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;

        int a = n, req = 0;
        int ans = 0;

        while (a) {
            int b = ilog(a, 3);  // floor(log base 3 of a)

            if (b == 0) {
                ans += 3;   // because ipow(3,0+1)=3, and (0 * ipow(3,-1)) = 0
                a -= 1;     // since c = 3^0 = 1
            } else {
                ans += ipow(3, b + 1) + (b * ipow(3, b - 1));
                int c = ipow(3, b);
                a -= c;
            }
            req++;
        }

        if (k < req) {
            cout << -1 << endl;
            continue;
        }
        if (k == req) {
            cout << ans << endl;
            continue;
        }
        if (k >= n) {
            cout << 3 * n << endl;
            continue;
        }

        int inti = iceil(n, k);   // safe ceil division
        int po = ilog_ceil(inti, 3);

        int excess = (k * ipow(3, po))-n;

        map<int, int> m;
        m[po]=k;
        // cout<<po<<" "<<m[po]<<endl;
        while (excess && po != 0) {
            int diff = ipow(3, po) - ipow(3, po - 1);
            int tobeconv = excess / diff;
            if (!tobeconv) break;
            m[po - 1] = tobeconv;
            m[po] -= tobeconv;
            excess -= tobeconv*diff ;
            po--;
        }
        // cout<<excess<<endl;
        if(m.find(0)!=m.end()){
            if(excess>m[0]){
                m[0]=0;
            }
            else{
                m[0]-=excess;
            }
        }

        ans = 0;
        for (auto &it : m) {
            // cout<<it.first<<" "<<it.second<<endl;
            if(it.first==0){
                ans+= 3*it.second;
            }
            else{
            ans += it.second * (ipow(3, it.first + 1) + (it.first * ipow(3, it.first - 1)));}
        }

        cout << ans << endl;  // final output
    }
}