#include<stdio.h>
//#define NMAX	1000L
//#define k7	2*3*5*7*11*13*17       // 510510
unsigned int v6[1236]={0,
30030,
39270,43890,46410,51870,53130,62790,66990,
67830,71610,72930,79170,81510,82110,84630,
85470,91770,94710,98670,99330,101010,102102,
103530,106590,108570,110670,111930,114114,115710,
117390,122430,123690,124410,125970,128310,129030,
132090,132990,136290,138138,140070,140910,144210,
144690,146370,147630,149226,149730,152490,153510,
154770,158730,161070,162690,163590,164010,166530,
167790,168630,170170,170430,171570,173910,174174,
175890,176358,178710,180642,181830,182490,182910,
184470,186186,187530,188790,189210,190190,191730,
192270,193830,194370,198030,199290,201630,201894,
205530,205590,207570,207690,210630,211470,213486,
214890,215670,217770,220110,222222,222870,224070,
225330,226590,227010,227370,227766,229710,230010,
230230,231990,233310,235290,235410,237930,238602,
239190,240870,241230,242970,243390,243474,245310,
246246,247170,248710,249690,251790,253110,253470,
254562,255255,255990,257070,258258,260130,260610,
261030,261690,261870,263670,264810,266910,267330,
269178,269610,271830,272118,274170,275730,277134,
278070,279930,280830,281010,281190,282030,282282,
283290,284970,285090,285285,286230,287430,287742,
290290,290598,291270,292110,293370,293930,294630,
294690,296310,296670,297330,297570,300390,300846,
301070,302610,303810,304590,305970,308154,308490,
310310,311190,311610,312018,313170,315210,316470,
317730,318318,318570,318630,321090,321594,322014,
322770,323610,324786,326370,329406,330990,331170,
331890,332310,334110,335478,336490,337722,338910,
340170,342210,342930,343434,344190,345030,345345,
346290,346710,348270,348810,350610,351390,352590,
354090,354354,355110,355810,356070,356730,357630,
358530,359310,359898,360570,362670,363630,364182,
365190,366366,367710,367770,369138,369930,370230,
370370,371490,373065,374010,374946,375870,376530,
377454,378510,379470,379610,380190,380562,381570,
381810,381990,382470,383838,384090,385710,385770,
387030,389130,389298,391170,392370,392730,393162,
393414,397110,397290,397670,398310,399126,399630,
400890,402270,402402,402990,403410,404430,404670,
405790,406410,406770,408030,409530,410410,410970,
411510,411810,412230,412566,413490,415338,416130,
416262,416670,418110,418470,419430,420090,420546,
421590,422994,424270,424410,425334,426426,426930,
428610,429870,430430,432390,433290,434010,434910,
435435,435666,436170,436254,437190,438438,439890,
440895,441210,441870,443190,444210,444570,444990,
445170,445830,446082,447330,447810,448630,449790,
450870,451605,452010,452166,453390,453530,455070,
455430,455910,456330,456918,457710,458430,458490,
459030,459690,461890,462210,462990,463386,463710,
464646,465234,465465,465630,467610,467670,468510,
470470,470730,472290,472758,473970,474474,475230,
475410,476238,478590,479094,479570,480810,480930,
481110,483990,484330,484770,485070,486330,487410,
487578,487830,488670,489090,490314,490854,491946,
494130,495330,495690,495726,496230,496470,497490,
498498,499290,499422,500610,501410,501942,504390,
504735,505362,505470,506730,507210,507990,508530,
509082,512430,513570,513590,514290,514878,515130,
516810,517902,519870,520030,520410,520590,521430,
522690,523110,523770,524370,525030,525210,526110,
526218,526470,526890,528990,529230,529914,530530,
531570,531930,532266,532770,533715,534534,535458,
535990,536690,537510,537810,538230,538890,539070,
539682,539994,540330,540930,541310,542010,542190,
543270,544170,544830,545790,546630,547170,547230,
547638,549010,549318,549822,550290,550830,551310,
551670,552090,554070,554610,555555,556206,556710,
557634,558030,559130,560490,561990,562870,563178,
563730,564630,566202,566610,567210,568230,568974,
569415,571710,572286,572390,573342,573870,576030,
576114,576870,577830,579390,579462,579810,581790,
581910,582330,582582,583338,583770,584970,585390,
585858,587202,587730,588126,590070,590226,590590,
590730,591090,591630,593670,594510,596190,596310,
596505,598026,599430,599610,599830,600270,600990,
602070,602490,603174,603570,605010,606390,606606,
606970,607530,607614,608190,608685,608790,610610,
611310,611490,611610,611754,612066,613410,613830,
615030,615090,615230,615615,615846,616170,617610,
618222,618618,619710,620310,620466,620490,621390,
621690,621894,623238,624030,624910,625170,626010,
626262,626430,626934,627198,627270,628530,629090,
629706,629970,631470,632730,632814,633270,633930,
634270,635910,635970,636090,636405,636870,637602,
639030,639210,639730,639870,640770,640794,641130,
641190,641886,642642,643110,644910,645645,645810,
646170,646646,647130,647790,648186,648210,648830,
649110,649194,649230,650370,651630,651882,652470,
653730,653790,654654,654810,655270,655690,656670,
657510,657930,659022,659190,659490,660858,661290,
661710,663810,665210,665574,666330,666930,667290,
668382,669630,670530,670670,670890,671370,672945,
673134,673302,673530,675510,676830,677586,677730,
678210,678678,678930,679098,679470,679830,680190,
680295,680862,681870,682890,683430,685230,685410,
685542,687570,687610,687990,688170,689010,689910,
690270,691530,692070,692230,692835,693462,693770,
693966,694830,695058,695130,696570,698610,699006,
699270,700770,700854,700910,700986,701610,703290,
704990,705705,706146,707370,708510,708630,708890,
709170,709410,709590,710094,710430,710710,710790,
711942,712470,713310,713370,714210,714630,715530,
716430,717090,717402,717990,718410,718770,718998,
719355,719670,720390,720510,722190,722670,723030,
724470,726110,726330,726495,727090,727818,728574,
729330,730158,730626,730730,732270,733278,734370,
734910,735042,735630,736230,736554,737490,739830,
740370,740922,742170,743070,743470,744198,744510,
744810,745710,746790,748374,748410,749190,749490,
751530,752070,752115,752514,753270,753610,753690,
754446,755790,756030,756210,757302,757770,758310,
759066,759810,761530,761838,762090,762762,763230,
764610,764790,765510,766038,766122,766194,766290,
766590,767130,767910,768570,770070,770385,770406,
771342,771834,772310,772590,773058,773430,773490,
773670,774410,775390,775698,776490,776910,778470,
779730,779790,780045,781014,781242,781770,782782,
783870,784770,785910,786030,786786,787290,787930,
788190,788766,789222,790230,790482,790790,791430,
792870,793254,793730,794010,794310,795522,795795,
796110,796290,797790,798270,798330,798490,799710,
799890,799986,800310,800394,801570,803010,803418,
803670,803985,804270,805035,806190,806610,807690,
808170,808962,809094,810030,810390,811410,811965,
812130,812490,812630,814506,815430,817190,817278,
817530,818070,818090,818958,819210,819390,819546,
819910,820410,821370,822030,822822,823515,825330,
825630,826098,826210,826770,827310,827526,827970,
828282,829290,830130,830490,830830,831390,831810,
832370,832830,834330,834834,835170,835590,835890,
836418,836570,837210,837330,837930,838110,838695,
839202,839454,840378,841386,841890,842010,842270,
844305,844998,845130,846510,846930,847110,847470,
847770,848470,848562,848946,849030,849090,851370,
851466,851730,852810,853230,853710,854490,856086,
856254,856290,857670,858130,858270,858390,858585,
858990,860370,860430,860574,861042,861630,862410,
862638,863170,864006,864570,864690,865410,865590,
866910,868434,868530,868686,869610,870090,870366,
871530,872610,873642,874038,874230,874874,875490,
875910,876090,876990,877030,878010,878370,878430,
879270,879690,880230,880770,881958,882570,883190,
884442,884730,885885,886578,886830,886890,887110,
887502,888810,889746,889770,890274,890358,890890,
891330,891618,891870,892430,893490,894102,894894,
896070,897078,897666,898590,899130,899470,899745,
899990,900354,902190,903630,904134,904470,904890,
905190,905730,905970,905982,906510,906870,906906,
907410,907494,908310,908922,909510,910455,910470,
912030,912730,913710,914430,915090,915306,915530,
915915,916370,916674,916734,917070,917490,919590,
919770,920010,920634,921270,921570,922530,922845,
923286,923790,923910,926310,926670,927010,927498,
928290,929390,929670,930090,930810,932178,932190,
932790,933702,934206,934230,935130,936510,936870,
937365,937482,938490,938630,938730,938910,939246,
939930,940470,941070,942942,943410,943635,943670,
944790,945438,945714,946110,946770,947310,948290,
948822,949494,950730,951258,951405,951510,951762,
952770,953610,953810,954822,955110,955570,956046,
956130,956670,956802,957030,957390,959574,959595,
959790,960190,960330,960630,961170,961590,961818,
962598,963186,963690,963930,964410,964590,965770,
965874,966210,966570,966810,967470,967890,968898,
969969,969990,970530,970710,970970,971490,972230,
972510,972762,972930,973182,973245,973590,973830,
975270,975390,976430,977262,977730,978054,978670,
978690,978810,978978,980070,980210,982410,982770,
982905,983010,983535,983710,984126,984270,984390,
985710,986790,986986,987690,987870,988494,988890,
989430,990318,990570,990930,991230,991914,992082,
992310,992670,993174,994290,994422,995106,995610,
996710,996870,997458,997815,997890,998070,998634,
998970,999570};
/*
unsigned int cautav6(unsigned int x)
{
unsigned int mij,st=0,dr=1234;
while(st<=dr){
	mij=(st+dr)/2;
	if(x==v6[mij]) return x;
	else if(x<v6[mij]) dr=mij-1;
		 else st=mij+1;
	}
if(x<v6[mij]) return v6[mij-1];
else return v6[mij+1];
} */


unsigned int cautav6(unsigned int x)
{
unsigned int i;
for(i=0;i<1236&&v6[i]<=x;i++)
	if(x==v6[i]) return x;
return v6[i-1];
}

int main()
{
unsigned int t,i,d,p,cmmn=1,pr[200]={0},nrp,n,k;
unsigned int min[8]={1,2,6,30,210,2310,30030,510510},y,cy,nrdiv,gata;
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);

pr[0]=1;
pr[1]=2;
nrp=2;
for(i=3;i<=1010;i=i+2){
	p=1;
	for(d=1;pr[d]*pr[d]<=i;d++)
		if(i%pr[d]==0) {p=0;break;}
	if(p) {pr[nrp]=i;nrp++;}
	}
scanf("%u",&t);

for(i=0;i<t;i++){
	scanf("%u%u",&n,&k);
	if(n==1)  /*cmmn=0;*/{ if(k==0) cmmn=1;  else cmmn=0;}
	else if(n==2)  //{if (k==1) cmmn=2;else cmmn=0;}
					 {if(k==0) cmmn=1; else if(k[i]==1)cmmn=2; else cmmn=0;}
		else{
			switch (k){
			case 0:cmmn=1;break;
		  //	case 6:cmmn=cautav6(n);break;
			case 7:if (n>=min[7]) cmmn=min[7];
				   else cmmn=0; break;

			default:
				//y=n[i];gata=0;
				//if(n[i]==min[k[i]]);// cmmn=y;
				//else
				{
					y=n;gata=1;
					while(gata&&y>=min[k]){
						if(y==min[k]) {gata=0;break;}
						nrdiv=0;
						cy=y;
						while(cy%2==0){nrdiv=1;cy/=2;}
						d=2; p=0;
						while(cy>1/*&&!p*/){
							if(cy%pr[d]==0){
								cy/=pr[d];
								nrdiv++;
								if(nrdiv>k) break;
								while(cy%pr[d]==0) cy/=pr[d];
								}
							d++;
							if(pr[d]*pr[d]>=cy&&cy>1){nrdiv++;break;/*p=1;*/}
							}
						if(nrdiv==k) gata=0;
						else y--;
					}
				if(gata) cmmn=0;
				else cmmn=y;
				}
			}
		}
	printf("%u\n",cmmn);
	}



return 0;
}