https://www.luogu.com.cn/record/134895888

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
inline ll read(){
	ll ans = 0;
	char c = getchar();
	while(c < '0' || c > '9'){
		c = getchar();
	}
	while('0' <= c && c <= '9'){
		ans = (ans<<3)+(ans<<1)+c-'0';
		c = getchar();
	}
	return ans;
}
inline void write(ll x){
	if(x == 0)return;
	write(x/10);
	putchar('0'+x%10); 
}
const ll mod = 998244353;
const ll mod1 = mod+1>>1;
const ll mod2 = (mod+1)/6;
ll dp[16][9][6][4][3][6005],cnt[105],jc[25];
inline ll dfs(int n,ll a,ll b,ll c,ll d,ll e,int k){
	if(a < 0 || b < 0 || c < 0 || d < 0 || e < 0 || k < 0)return 0;
	if(k == 0)return !(a || b || c || d || e);
	if(~dp[a][b][c][d][e][k])return dp[a][b][c][d][e][k];
	int p = a+b+c+d+e;
	p = p*(n-p+1);
	dp[a][b][c][d][e][k] = 0;
	dp[a][b][c][d][e][k] += dfs(n,a-1,b,c,d,e,k-1*p);
	dp[a][b][c][d][e][k] %= mod;
	dp[a][b][c][d][e][k] += dfs(n,a,b-1,c,d,e,k-2*p);
	dp[a][b][c][d][e][k] %= mod;
	dp[a][b][c][d][e][k] += dfs(n,a,b,c-1,d,e,k-3*p);
	dp[a][b][c][d][e][k] %= mod;
	dp[a][b][c][d][e][k] += dfs(n,a,b,c,d-1,e,k-4*p);
	dp[a][b][c][d][e][k] %= mod;
	dp[a][b][c][d][e][k] += dfs(n,a,b,c,d,e-1,k-5*p);
	dp[a][b][c][d][e][k] %= mod;
	return dp[a][b][c][d][e][k];
}
inline ll ans1(ll n,ll m){
	n %= mod;
	m %= mod;
	ll ans = ((((n+1)*m)%mod*(m+1))%mod*mod1)%mod;
	ans -= (((m*(m+1))%mod*(2*m+1))%mod*mod2)%mod;
	return (ans+mod)%mod;
}
inline ll ans2(ll n){
	//n %= mod;
	ll m = n>>1,ans = 0,t;
	for(int i = 0;i < 63;i++)cnt[i+1] = n>>i;
	for(int i = 1;i < 63;i++)cnt[i] -= cnt[i+1];
	if(n%2 == 1){
		ans = ((m+1)*(n-m))%mod;
		cnt[1]--;
	}
	for(int i = 1;i <= 63;i++){
		t = cnt[i]>>1;
		m -= t;
		ans = (ans+(2*(ans1(n,m+t)-ans1(n,m)+mod)%mod*i)%mod)%mod;
		if(cnt[i]%2 == 1){
			ans = (ans+m%mod*((n-m+1)%mod)%mod*i%mod)%mod;
			ans = (ans+m%mod*((n-m+1)%mod)%mod*(i+1)%mod)%mod;
			cnt[i+1]--;
			m--;
		}
	}
	for(int i = 0;i < 63;i++)cnt[i+1] = n>>i;
	for(int i = 1;i < 63;i++)cnt[i] -= cnt[i+1];
	return ans%mod;
} 
int q;
ll n,k,x,y;
int main(){
	q = read();
	jc[0] = 1;
	for(ll i = 1;i <= 15;i++){
		jc[i] = jc[i-1]*i;
	}
	for(int i = 1;i <= q;i++){
		n = read();
		k = read();
		x = ans2(n);
		if(n > 28){
			if(x == 0)putchar('0');
			else write(x);
			putchar('\n');
			continue;
		}
		for(int j = 1;j <= 5;j++){
			k = (k-1)/jc[cnt[j]]+1;
		}
		memset(dp,0xff,sizeof(dp));
		while(true){
			y = dfs(n,cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],x);
//printf("[note]y=%lld\n",y);
			if(y >= k){
				if(x == 0)putchar('0');
				else write(x);
				putchar('\n');
				break;
			}
			k -= y;
			x++;
			x %= mod;
		}
	}
	return 0;
}
//GodMode.{ED7BA470-8E54-465E-825C-99712043E01C}