#include <bits/stdc++.h>
using namespace std;
#define int long long
int cost[16] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 6, 5, 4, 5, 5, 4}, pre[17];
constexpr int up = 1ll << 32;
int solve(int n) {
	if (n == up) {
		return 8 * (1ll << 28) * pre[16];
	}
	int res = 0, s = 0;
	for (int i = 7; i >= 0; i--) {
		int d = n >> (i * 4) & 15;
		res += s * d * (1ll << (4 * i));
		res += pre[d] * (1ll << (4 * i));
		if (i) {
			res += d * i * pre[16] * (1ll << (4 * (i - 1)));
		}
		s += cost[d];
	}
	return res;
}
void solve() {
	int n;
	cin >> n;
	int a = 0;
	for (int i = 0; i < 8; i++) {
		a *= 16;
		char c;
		cin >> c;
		if (isdigit(c)) {
			a += c - '0';
		} else {
			a += 10 + c - 'A';
		}
	}
	int r = a + n;
	if (r >= up) {
		cout << solve(r - up) + solve(up) - solve(a) << "\n";
	} else {
		cout << solve(r) - solve(a) << "\n";
	}
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	for (int i = 0; i < 16; i++) {
		pre[i + 1] = pre[i] + cost[i];
	}
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}