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

ll cost[16]={6,2,5,5,4,5,6,3,7,6,6,5,4,5,5,4},pw[55];

ll tov(ll w){
	if (isdigit(w))return w-'0';
	return w-'A'+10;
}

ll dig[8];
ll solve(ll v,ll n){
	for (ll i=0;i<8;i++)dig[i]=v/pw[i]%16;
	ll rel=0;
	ll sm=0;
	for (ll j=0;j<16;j++)sm+=cost[j];
	for (ll i=0;i<8;i++){
		ll lim=pw[i],ss=0;
		for (ll j=0;j<i;j++)ss+=dig[j]*pw[j];	
		ll nd=lim-ss;
		ll pn=n;
		rel+=min(nd,pn)*cost[dig[i]];
		pn-=min(nd,pn);
		rel+=pn/pw[i+1]*sm;
		pn%=pw[i+1];
		for (ll j=(dig[i]+1)%16;j!=dig[i];j=(j+1)%16){
			rel+=min(pn,pw[i])*cost[j];
			pn-=min(pn,pw[i]);
		}
	}
	return rel;
}

int main(){
	ll t;
	cin >> t;
	pw[0]=1;
	for (ll i=1;i<=8;i++)pw[i]=pw[i-1]*16;
	ll mx=0;
	for (ll i=0;i<8;i++)mx+=pw[i]*15;
	while (t--){
		ll n;
		cin >> n;
		string m;
		cin >> m;
		reverse(m.begin(),m.end());
		ll pv=0;
		for (ll i=0;i<8;i++)pv+=tov(m[i])*pw[i];
		if (pv+n>mx){
			ll dif=mx-pv;
			cout<< solve(pv,dif+1)+solve(0,n-dif-1)<<"\n";
		}else{
			cout<< solve(pv,n)<<"\n";
		}
	}
	return 0;
}

/*
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　■■■■■　　　　　■■　　　　　　■■■　　　　　■■■　　　■　　　　■　　　　　■　　　　　■■■■　　　　■■■■　　
　■　　　■■　　　　■■　　　　　■　　■■　　　■　　■■　　■　　　　■　　　　■■　　　　　■　　■■　　■■　　■　　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　■■■　　　　■■　　■■　　■　　　■■　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　　■■　　　　■　　　■■　　　　　　■■　
　■　　　　■　　　　■■　　　　■　　　　　　　■　　　　　　　　　■■　　　　　　■■　　　　　　　　■■　　　　　　■　　
　■　　　■■　　　　■■　　　　■　　■■■　　■　　■■■　　　　■■　　　　　　■■　　　　　　　■■　　　　　■■■　　
　■■■■■　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　　■■　　　　　　　　■■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■■　　　　　　　　　　■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■　　　　　　■　　　■■　
　■　　　　　　　　　■■　　　　■■　　■■　　■■　　■■　　　　■■　　　　　　■■　　　　■　　　　　　　■■　　■■　
　■　　　　　　　　　■■　　　　　　■■■■　　　　■■■■　　　　■■　　　　　　■■　　　　■■■■■■　　　■■■■　　
*/