#include<fstream.h>

  ifstream f("divprim.in");
  ofstream g("divprim.out");
  int x[7]={2,3,5,7,11,13,17},j,b;
  long p,n,i,a;
int main()
{
 f>>n;
 for(i=1;i<=n;i++)
 {
  f>>a;
  f>>b;
  if(b==0)
	g<<1;
  if(b==1 && a>=9)
	g<<9<<"\n";
  if(b==1 && a<9)
	 g<<0<<"\n";
  if(b!=1)
  {
	p=1;
	for(j=0;j<=b-1;j++)
	p=p*x[j];
	if(p<=a)
    {
    p=a%p;
    p=a-p;
    	 g<<p<<"\n";
	}
     else g<<0<<"\n";
  }
 }
 f.close();
 g.close();
 return 0;
}