#include<stdio.h>
long long ans,s[1001][1001];
int T,n,m,hs[1001][1001];
long long fs(long long nn,long long k);
int main()
{
	FILE *in=fopen("piggy.in","r");
	FILE *out=fopen("piggy.out","w");
	int k;
	fscanf(in,"%d",&T);
	for(k=1;k<=T;k++)
	{
		fscanf(in,"%d %d",&n,&m);
		ans=fs(n,m);
		fprintf(out,"%lld\n",ans);
		}
	return 0;
	}
long long fs(long long nn,long long k)
{
	if(hs[nn][k]) return s[nn][k]; 
	if(nn==k||k==1) return 1;
	else if(k>nn||nn==0||k==0) return 0;
	s[nn][k]=fs(nn-1,k-1)+k*fs(nn-1,k);
	hs[nn][k]=1;
	return s[nn][k];
	}