/*
* Author: Xiangmy
* Created: 2024-04-01 20:11
* Problem: 
* Description: 
*/
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << (x) << ' '
// #define x first
// #define y second
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 200;
typedef pair<int, int> PII;

vector<int> num(N);
LL dp[N][N];

LL mp[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 6, 5, 4, 5, 5, 4};

LL dfs(int pos, LL v, bool limit) {
    if (pos == 0) return v;
    if (!limit && dp[pos][v] != -1) return dp[pos][v];
    LL res = 0;
    int up = (limit ? num[pos] : 15);
    for (int i = 0; i <= up; ++ i) {
        res += dfs(pos - 1, v + mp[i], limit && i == up);
    }
    if (!limit) dp[pos][v] = res;
    return res;
}

LL work(LL x) {
    for (int i = 1; i <= 8; ++ i) {
        num[i] = x % 16;
        x /= 16;
    }
    memset(dp, -1, sizeof dp);
    return dfs(8, 0, true);
}

void solve() {
    LL t; string s; cin >> t >> s;
    LL st = 0;
    for (int i = 0; i <= 7; ++ i) {
        st *= 16;
        if (isdigit(s[i])) st += s[i] - '0';
        else st += s[i] - 'A' + 10;
    }
    LL ed = st + t - 1;
    LL ans = 0;
    if (ed <= (1ll << 32) - 1) {
        ans += work(ed);
    } else {
        ans += work(ed % (1ll << 32));
        ans += work((1ll << 32) - 1);
    }
    ans -= work(st - 1);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  // 交互题不用
    cout.tie(0);
    // cout << fixed << setprecision(6);
    // cout << setw(4) << setfill('0');
    
    int T = 1;
    cin >> T;
    while (T -- ) {
        // cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
        solve();
    }
    return 0;
}