#include <bits/stdc++.h>
using namespace std;

void justDoIt();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    justDoIt();
    return 0;
}

typedef unsigned long long ull;

int charToHex(char c) {
    if ('0' <= c && c <= '9') {
        return c - '0';
    }
    else {
        return 10 + (c - 'a');
    }
}

char hexToChar(int d) {
    if (0 <= d && d <= 9) {
        return (char)('0' + d);
    }
    else {
        return (char)('a' + (d - 10));
    }
}

ull read(char base) {
    if (base == 10) {
        ull res;
        cin >> res;
        return res;
    }
    else {
        ull res = 0;
        string s;
        cin >> s;
        for (auto c: s) {
            res = res * base + charToHex(c);
        }
        return res;
    }
}

void print(int base, ull res) {
    if (res == -1ULL) {
        cout << '-' << '\n';
        return;
    }
    if (base == 10) {
        cout << res << '\n';
        return;
    }
    else {
        string s = "";
        while (res) {
            s += hexToChar(res % base);
            res /= base;
        }
        if (s.empty()) {
            s = "0";
        }
        reverse(s.begin(), s.end());
        cout << s << '\n';
        return;
    }
}

ull calc0(int base, ull r) {
    if (r == 0) {
        return 1;
    }
    if (r != -1ull) {
        r++;
    }
    vector<int> digits;
    ull cur = r;
    while (cur) {
        digits.push_back(cur % base);
        cur /= base;
    }
    reverse(digits.begin(), digits.end());
    int len = digits.size();
    ull res = 1;
    for (int i = 1; i < len; i++) {
        ull ways = base - 1;
        for (int j = base - 1; j >= base - i + 1; j--) {
            ways *= j;
        }
        res += ways;
    }
    vector<bool> flag(base);
    for (int i = 0; i < len; i++) {
        ull ways = 1;
        int rem = base - (i + 1);
        int suf = len - (i + 1);
        for (int k = rem; k >= rem - suf + 1; k--) {
            ways *= k;
        }
        for (int j = (i == 0 ? 1 : 0); j < digits[i]; j++) {
            if (!flag[j]) {
                res += ways;
            }
        }
        if (flag[digits[i]]) {
            break;
        }
        flag[digits[i]] = true;
    }
    return res;
}

ull calc1(int base, ull pos) {
    if (pos == 1) {
        return 0;
    }
    pos--;
    ull ways = base - 1;
    int len = 1;
    for (; len <= base; len++) {
        if (pos > ways) {
            pos -= ways;
        }
        else {
            break;
        }
        ways *= base - len;
    }
    if (len > base) {
        return -1;
    }
    pos--;
    vector<ull> suf(len + 1);
    for (int i = 0; i < len; i++) {
        suf[i] = base - i;
    }
    suf[len] = 1;
    for (int i = len - 1; i >= 0; i--) {
        suf[i] *= suf[i + 1];
    }
    vector<int> order(len);
    for (int i = 0; i < len; i++) {
        order[i] = pos / suf[i + 1];
        pos %= suf[i + 1];
    }
    vector<bool> flag(base);
    ull res = 0;
    for (int i = 0; i < len; i++) {
        int cnt = order[i];
        for (int d = (i == 0 ? 1 : 0); d < base; d++) {
            if (!flag[d]) {
                if (cnt == 0) {
                    res = res * base + d;
                    flag[d] = true;
                    break;
                }
                cnt--;
            }
        }
    }
    return res;
}

void test() {
    char b;
    cin >> b;
    int base = (b == 'd' ? 10 : 16);
    int type;
    cin >> type;
    if (type == 0) {
        ull l = read(base);
        ull r = read(base);
        ull res = calc0(base, r) - (l == 0 ? 0 : calc0(base, l - 1));
        print(base, res);
    }
    else {
        ull pos = read(base);
        ull res = calc1(base, pos);
        print(base, res);
    }
}

void justDoIt() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        test();
    }
}