网易互娱题解

	/*
#include <iostream>
using namespace std;
int main(void) {
    int n;
    cin >> n;
    while(n--) {
        string s;
        string sol;
        int m = 1;
        cin >> s;
        int st = 0;
        for(int i = 1; i < s.size(); ++i) {
            if(s[i] == s[i - 1] + 1) {
                ++m;
            }else {
                if(m >= 4) {
                    sol += s[st];
                    sol += '-';
                    sol += s[i - 1];
                }else {
                    for(int j = st; j < i; ++j) {
                        sol += s[j];
                    }
                }
                m = 1;
                st = i;
            }
        }
        if(m >= 4) {
            sol += s[st];
            sol += '-';
            sol += s[s.size() - 1];
        }else {
            for(int i = st; i < s.size(); ++i) {
                sol += s[i];
            }
        }
        cout << sol << endl;
    }
    return 0;
}
*/
/*
#include <iostream>
using namespace std;
const int MAXN = 2e3 + 10;
struct gel {
    string time;
    int num;
    string world;
}a[MAXN];
int main(void) {
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> a[i].time >> a[i].num >> a[i].world;
    }
    int q;
    cin >> q;//100
    while(q--) {
        int k;
        cin >> k;
        int af = -1, bf = -1, ber = -1;
        string key;
        while(k--) {
            string str;
            cin >> str;
            if(str == "--search") cin >> key;
            else if(str == "--hostid") cin >> ber;
            else if(str == "--before") cin >> bf;
            else cin >> af;
        }
        int sol = -1;
        for(int i = 0; i < n; ++i) {
            if(a[i].world.find(key) != -1) {
                if(ber != -1) {
                    if(a[i].num == ber) {
                        sol = i;
                        break;
                    }
                }else {
                    sol = i;
                    break;
                }
            }
        }
        if(sol == -1) {
            cout << "ERROR" << endl;
            continue;
        }
        if(bf != -1) {
            int indx = max(0, sol - bf);
            for(int i = indx; i < sol; ++i) {
                cout << a[i].world << endl;
            }
        }
        cout << a[sol].world << endl;
        if(af != -1) {
            int indx = min(n, sol + af + 1);
            for(int i = sol + 1; i < indx; ++i) {
                cout << a[i].world << endl;
            }
        }
    }
    return 0;
}
*/

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#define ll long long
using namespace std;
const int MAXN = 1e3;
ll vis1[MAXN];
ll vis2[MAXN];
int main(void) {
    int t;
    cin >> t;
    while(t--) {//100
        int a, b;
        string s;
        memset(vis1, 0, sizeof(vis1));
        memset(vis2, 0, sizeof(vis2));
        cin >> a >> b >> s;       
        int len = s.size();
        vis1[0] = s[0] - '0';
        if(s[0] >= 'A') vis1[0] = s[0] - 'A' + 10;
        for(int i = 1; i < len; ++i) {
            int cnt = s[i] - '0';
            if(s[i] >= 'A') {
                cnt = s[i] - 'A' + 10;
            }
            vis1[i] = vis1[i - 1] * a + cnt;
        }
        // for(int i = 0; i < len; ++i) {
        //     cout << vis1[i] << " " << endl;
        // }
        // cout << "===" << endl;
        ll pow = b;
        vis2[len - 1] = s[len - 1] - '0';
        if(s[len - 1] >= 'A') vis2[len - 1] = s[len - 1] - 'A' + 10;
        for(int i = len - 2; i >= 0; --i) {
            int cnt = s[i] - '0';
            if(s[i] >= 'A') {
                cnt = s[i] - 'A' + 10;
            }
            vis2[i] = vis2[i + 1] + pow * cnt;
            pow *= b;
        }
        // for(int i = len - 1; i >= 0; --i) {
        //     cout << vis2[i] << endl;
        // }
        // cout << endl;
        for(int i = 0; i < len; ++i) {
            if(vis2[i + 1] == vis1[i]) {
                cout << vis1[i] << endl;
                break;
            }
        }
    }
    return 0;
}