#include<fstream.h>
ifstream intrare ("divprim.in");
ofstream iesire ("divprim.out");
int v[200],sol[10000];
void ciur()
{
	int q=2,sw=0;  v[1]=2;
	for(int i=3;i<=998;i+=2)
	{
		sw=0;
		for(int j=2;j<=i/2+1;j++)
		{
			if(i%j==0) sw=1;
		}
		if(sw==0) { v[q]=i; q++; }
	}
}
void verificare(int n, int k)
{
	int rest;
	for (int i=1;i<=169;i++)
	{
		if(v[i]<=n/2)
		{
		rest=n%v[i];
		rest=n-rest;
		while(rest!=0)
		{
			sol[n-rest]++;
			rest-=v[i];
		}
		}
		else i=175;
	}
	int sw=0;
	for(i=0;i<=n;i++) if(sol[i]==k){ iesire<<n-i<<"\n"; i=n+3; sw=1;}
	if( sw==0) iesire<<0<<"\n";
	for(i=0;i<=n;i++) sol[i]=0;
}
int main()
{
	int t,n,k;
	intrare>>t;
	ciur();
	for(int s=1;s<=t;s++)
	{
		intrare>>n>>k;
		if(n==1) iesire<<0<<"\n";
		else verificare(n,k);
	}
	return 0;
}