#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <ranges>
#include <sstream>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

using i64 = long long;
using u64 = std::uint64_t;

std::vector<u64> fact;

u64 npk(int n, int k) {
    return fact[n] / fact[n - k];
}
u64 counting(std::vector<int> b, int D) {
    u64 ans = 0;
    if(b.size() <= D) {
        std::vector<int> vis(D);
        for(int i = 0; i < b.size(); i++) {
            u64 n = b[i];
            u64 c = 0;
            for(int j = (i == 0 ? 1 : 0); j < n; j++) {
                if(!vis[j]) c++;
            }
            ans += c * npk(D - i - 1, b.size() - i - 1);
            if(i > 0) {
                ans += (D - 1) * npk(D - 1, b.size() - 1 - i);
            }
            if(vis[n]) break;
            vis[n] = 1;
            if(i + 1 == b.size()) ans++;
        }
    }
    else {
        for(int i = 1; i <= D; i++) {
            ans += (D - 1) * npk(D - 1, i - 1);
        }
    }
    ans++;
    return ans;
}

std::vector<int> conv(const std::string& a) {
    if(a == "0") {
        return {};
    }
    std::vector<int> x(a.size());
    for(int i = 0; i < a.size(); i++) {
        if('a' <= a[i] && a[i] <= 'f') {
            x[i] = (10 + a[i] - 'a');
        }
        else {
            x[i] = a[i] - '0';
        }
    }
    return x;
}

std::vector<int> vms(std::vector<int> x, int D) {
    for(int i = x.size(); i --> 0;) {
        if(x[i] > 0) {
            x[i]--;
            break;
        }
        x[i] = D - 1;
    }
    if(x.front() == 0) {
        x.erase(x.begin());
    }
    return x;
}

void solve() {
    char c;
    std::cin >> c;
    int mode = 0;
    int D = c == 'h' ? 16 : 10;
    std::cin >> mode;
    if(mode == 0) {
        std::string a, b;
        std::cin >> a >> b;
        auto x = conv(a);
        auto y = conv(b);
        u64 p = (a == "0" ? 0 : counting(vms(x, D), D));
        u64 q = counting(y, D);
        if(c == 'h') std::cout << std::hex;
        std::cout << q - p << std::dec << std::endl;
    }
    else {
        
        std::string a;
        std::cin >> a;
        auto x = conv(a);
        u64 obj = 0;
        for(u64 c: x) {
            obj = obj * D + c;
        }

        if(obj == 1) {
            std::cout << 0 << std::endl;
            return;
        }
        u64 ok = ~(u64(0));
        u64 ng = 0;
        while((ok - ng) > 1) {
            u64 mid = ng + (ok - ng) / 2;
            std::stringstream ss;
            if(c == 'h') ss << std::hex;
            ss << mid;
            u64 p = counting(conv(ss.str()), D);
            if(p >= obj) {
                ok = mid;
            }
            else {
                ng = mid;
            }
        }
        if(ok == ~0) {
            std::cout << "-" << std::endl;
        }
        else {
            if(c == 'h') std::cout << std::hex;
            std::cout << ok << std::dec << std::endl;
        }
    }
}

int main() {
    fact.resize(20);
    fact[0] = 1;
    for(int i = 1; i < 20; i++) {
        fact[i] = fact[i - 1] * i;
    }
    int T;
    std::cin >> T;
    while(T--) solve();
}