#include<bits/stdc++.h>
using namespace std;
int num,T,x,y,answer,i,j,a[1000010],b[1000010],c[1000010];
void dcf()
{
	for(int i=a[0];i>=1;i--)
		for(int j=b[0];j>=1;j--)
			c[a[0]-i+b[0]-j+1]+=a[i]*b[j];
	for(int i=1;i<=a[0]+b[0];i++)
	{
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	int k=0;
	num=a[0]+b[0];
	for(int i=a[0]+b[0];i>=1;i--)
	{
		if(k==0 && c[i]==0 && i>1)
		{
			num--;
			continue;
		}
		else k=1;
		b[num-i+1]=c[i];
	}
	memset(c,0,sizeof(c));
	b[0]=num;
}
void translate(int x)
{
	int t=0;
	while(x>0)
	{
		a[++t]=x%10;
		x/=10;
	}
	a[0]=t;
	for(int i=1;i<=t/2;i++)
		swap(a[i],a[t-i+1]);
	dcf();
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)
	{
		answer=0;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		b[0]=1;
		b[1]=1;
		cin>>x>>y;
		for(int i=1;i<=x;i++)
			translate(i);			
		int flag=0;
		for(int i=num;i>=1;i--)
			if(b[i]==y) answer++;
		cout<<answer<<"\n";
	}
}