#include<stdio.h>
//#define NMAX 1000L
//#define k7 2*3*5*7*11*13*17 // 510510
unsigned int v6[2342]={0,
30030,
39270,43890,46410,51870,53130,60060,62790,
66990,67830,71610,72930,78540,79170,81510,
82110,84630,85470,87780,90090,91770,92820,
94710,98670,99330,101010,102102,103530,103740,
106260,106590,108570,110670,111930,114114,115710,
117390,117810,120120,122430,123690,124410,125580,
125970,128310,129030,131670,132090,132990,133980,
135660,136290,138138,139230,140070,140910,143220,
144210,144690,145860,146370,147630,149226,149730,
150150,152490,153510,154770,155610,157080,158340,
158730,159390,161070,162690,163020,163590,164010,
164220,166530,167790,168630,169260,170170,170430,
170940,171570,173910,174174,175560,175890,176358,
178710,180180,180642,181830,182490,182910,183540,
184470,185640,186186,187530,188370,188790,189210,
189420,190190,191730,192270,193830,194370,196350,
197340,198030,198660,199290,200970,201630,201894,
202020,203490,204204,205530,205590,207060,207480,
207570,207690,210210,210630,211470,212520,213180,
213486,214830,214890,215670,217140,217770,218790,
219450,220110,221340,222222,222870,223860,224070,
225330,226590,227010,227370,227766,228228,229710,
230010,230230,231420,231990,232050,233310,234780,
235290,235410,235620,237510,237930,238602,239190,
240240,240870,241230,242970,243390,243474,244530,
244860,245310,246246,246330,247170,247380,248710,
248820,249690,251160,251790,251940,253110,253470,
253890,254562,255255,255990,256410,256620,257070,
258060,258258,259350,260130,260610,261030,261690,
261870,263340,263670,264180,264810,265650,265980,
266910,267330,267960,269178,269610,270270,271320,
271830,272118,272580,274170,274890,275310,275730,
276276,277134,278070,278460,279930,280140,280830,
281010,281190,281820,282030,282282,283290,284130,
284970,285090,285285,286230,286440,287430,287742,
288420,289380,290290,290598,291270,291720,292110,
292740,293370,293930,294630,294690,295260,296010,
296310,296670,297330,297570,297990,298452,299460,
300300,300390,300846,301070,302610,303030,303810,
304590,304980,305970,306306,307020,307230,308154,
308490,309540,310310,310590,311190,311220,311610,
312018,313170,313950,314160,315210,316470,316680,
317460,317730,318318,318570,318630,318780,319770,
321090,321594,322014,322140,322770,323610,324786,
324870,325380,325710,326040,326370,327180,328020,
328440,329406,330330,330990,331170,331890,332010,
332310,333060,334110,334950,335478,335580,335790,
336490,337260,337722,338520,338910,339150,340170,
340340,340860,341880,342210,342342,342930,343140,
343434,344190,345030,345345,346290,346710,347130,
347820,348270,348348,348810,350610,351120,351390,
351780,352170,352590,352716,353430,354090,354354,
355110,355810,356070,356730,357420,357630,358050,
358530,359310,359898,360360,360570,361284,362670,
363090,363630,363660,364182,364650,364980,365190,
365820,366366,367080,367290,367710,367770,368940,
369138,369930,370230,370370,371070,371280,371490,
371910,372372,373065,373230,374010,374946,375060,
375870,376530,376740,377454,377580,377910,378420,
378510,378840,379470,379610,380190,380380,380562,
381570,381810,381990,382470,383460,383838,384090,
384540,384930,385710,385770,387030,387090,387660,
388740,389130,389298,390390,391170,392370,392700,
392730,393162,393414,394680,395010,395850,396060,
396270,397110,397290,397320,397670,398310,398580,
398970,399126,399630,400890,401940,402270,402402,
402990,403260,403410,403788,404040,404430,404670,
405790,406410,406770,406980,407550,408030,408408,
408870,409530,410410,410550,410970,411060,411180,
411510,411810,412230,412566,413490,414120,414414,
414960,415140,415338,415380,416130,416262,416670,
417690,418110,418470,419430,420090,420210,420420,
420546,421260,421590,422730,422940,422994,423150,
424270,424410,425040,425334,426360,426426,426930,
426972,427350,428610,429660,429780,429870,430430,
431340,431970,432390,432630,433290,434010,434070,
434280,434910,435435,435540,435666,436170,436254,
437190,437580,438438,438900,439110,439530,439890,
440220,440895,441210,441870,442680,442890,443190,
444210,444444,444570,444990,445170,445740,445830,
446082,447330,447678,447720,447810,448140,448630,
449190,449790,450450,450660,450870,451605,452010,
452166,453180,453390,453530,454020,454740,455070,
455430,455532,455910,456330,456456,456918,457470,
457710,458430,458490,458850,459030,459420,459690,
460020,460460,460530,461890,462210,462840,462990,
463386,463710,463980,464100,464310,464646,465234,
465465,465630,466620,466830,467610,467670,468510,
468930,469560,470470,470580,470730,470820,471240,
472290,472758,473550,473970,474474,474810,475020,
475230,475410,475860,476190,476238,477204,478170,
478380,478590,479094,479570,480480,480810,480930,
481110,481740,482460,482790,483210,483990,484330,
484770,485070,485940,486330,486780,486948,487410,
487578,487830,488070,488670,489060,489090,489720,
490314,490620,490770,490854,491946,492030,492492,
492660,493350,494130,494340,494760,495330,495690,
495726,496230,496470,496650,497420,497490,497640,
498498,499290,499380,499422,499590,500610,501270,
501410,501942,502320,503370,503580,503880,504390,
504735,505050,505362,505470,505890,506220,506730,
506940,507210,507780,507990,508530,509082,509124,
510510,510510,510510,510510,510510,510510,510510,
511290,511980,512430,512820,513240,513570,513590,
514140,514290,514710,514878,515130,516120,516516,
516810,517650,517902,518700,519870,520030,520260,
520410,520590,521220,521430,521730,522060,522522,
522690,523110,523380,523740,523770,524370,525030,
525210,526110,526218,526470,526680,526890,527340,
527670,528360,528990,529074,529230,529620,529914,
530530,531300,531570,531930,531960,532266,532770,
532950,533715,533820,534534,534660,535458,535920,
535990,536130,536690,537510,537810,538230,538356,
538890,539070,539220,539682,539994,540330,540540,
540930,541310,541926,542010,542190,542640,542850,
543270,543660,544170,544236,544830,545160,545490,
545790,546630,547170,547230,547470,547638,548340,
548730,549010,549318,549780,549822,550290,550620,
550830,551310,551460,551670,552090,552552,553350,
553410,554070,554190,554268,554610,555555,556140,
556206,556710,556920,557634,558030,558558,559130,
559650,559860,560280,560490,561660,561990,562020,
562380,562590,562870,563178,563640,563730,564060,
564564,564630,565110,566202,566370,566580,566610,
567210,567630,568230,568260,568974,569415,569940,
570180,570570,570570,570570,570570,570570,570570,
570570,571710,572286,572390,572460,572880,573342,
573870,574770,574860,575190,575484,576030,576114,
576810,576840,576870,577830,578550,578760,579390,
579462,579810,580580,581196,581490,581790,581910,
582330,582540,582582,583110,583338,583440,583770,
584220,584430,584970,585390,585480,585858,586740,
586950,587202,587730,587860,588126,589050,589260,
589380,590070,590226,590520,590590,590730,591090,
591630,592020,592410,592620,593340,593670,594090,
594510,594660,595140,595980,596190,596310,596505,
596904,597870,598026,598290,598920,599430,599610,
599830,600270,600600,600780,600990,601692,602070,
602140,602490,602910,603174,603330,603570,604890,
605010,605220,605682,606060,606390,606606,606970,
607530,607614,607620,608190,608685,608790,609180,
609960,610470,610610,611310,611490,611610,611754,
611940,612066,612150,612612,613410,613830,614040,
614460,615030,615090,615230,615615,615846,616170,
616308,616590,616770,616980,617610,618222,618450,
618618,619080,619710,620310,620466,620490,620620,
621180,621390,621690,621894,622050,622380,622440,
622710,623070,623220,623238,624030,624036,624910,
625170,626010,626262,626340,626430,626934,627198,
627270,627900,628320,628530,629090,629706,629850,
629970,630420,630630,631470,631890,632730,632814,
632940,633270,633360,633930,634270,634410,634920,
635460,635910,635970,636090,636405,636636,636870,
637140,637260,637560,637602,639030,639210,639540,
639730,639870,640458,640770,640794,641130,641190,
641550,641886,642180,642390,642642,643110,643188,
644028,644280,644490,644670,644910,645150,645540,
645645,645810,646170,646646,647010,647130,647220,
647790,648186,648210,648830,649110,649194,649230,
649572,649740,650370,650760,651420,651630,651882,
652080,652470,652740,653310,653730,653790,654360,
654654,654810,655270,655690,656040,656370,656670,
656880,657510,657930,658350,658812,659022,659190,
659490,660330,660450,660660,660858,661290,661710,
661980,662340,662970,663780,663810,664020,664620,
664950,665210,665574,666120,666330,666666,666930,
667290,667590,668220,668382,668610,669630,669900,
670530,670670,670890,670956,671160,671370,671580,
672210,672945,672980,673134,673302,673530,674310,
674520,675444,675510,675990,676830,677040,677586,
677730,677820,678210,678300,678678,678930,679098,
679470,679770,679830,680190,680295,680340,680680,
680862,681030,681450,681720,681870,682110,682890,
683298,683430,683760,684420,684684,685230,685410,
685542,685860,686280,686868,687570,687610,687990,
688170,688380,689010,689130,689910,690030,690060,
690270,690690,690690,690690,690690,690690,690690,
690690,691530,692070,692230,692580,692835,693420,
693462,693770,693966,694260,694830,695058,695130,
695310,695640,695970,696150,696540,696570,696696,
697620,698610,699006,699270,699930,700350,700770,
700854,700910,700986,701220,701610,702240,702780,
703290,703560,704340,704550,704990,705180,705432,
705705,705870,706146,706230,706860,707070,707370,
708180,708510,708630,708708,708890,709170,709410,
709590,710094,710220,710430,710710,710790,711620,
711942,712140,712470,712530,713310,713370,713460,
713790,714210,714630,714714,714840,715260,715530,
715806,716100,716430,717060,717090,717402,717570,
717990,718410,718620,718770,718998,719355,719670,
719796,720390,720510,720720,721050,721140,722190,
722568,722610,722670,723030,723450,723690,724470,
724710,725340,726110,726180,726330,726495,727090,
727260,727320,727818,728364,728574,728910,729300,
729330,729960,730158,730170,730380,730422,730626,
730730,731640,731850,732270,732732,733278,733590,
734160,734370,734580,734910,735042,735420,735540,
735630,735930,736230,736554,736890,737490,737880,
738150,738276,738738,738990,739830,739860,740370,
740460,740740,740922,741510,742140,742170,742560,
742980,743070,743470,743820,744198,744510,744744,
744810,745710,746130,746130,746130,746130,746130,
746130,746130,746460,746790,748020,748374,748410,
748650,749070,749190,749490,749892,750120,750750,
751530,751740,752070,752115,752514,753060,753270,
753480,753610,753690,754446,754908,755160,755370,
755790,755820,756030,756210,756840,757020,757302,
757680,757770,758310,758940,759066,759220,759330,
759810,759990,760380,760410,760760,761124,761530,
761670,761838,762090,762450,762762,763140,763230,
763620,763686,763980,764610,764790,764940,765510,
765765,766038,766122,766194,766290,766590,766920,
767130,767550,767676,767910,767970,768180,768570,
769080,769230,769860,770070,770385,770406,771210,
771342,771420,771540,771834,772310,772590,773058,
773430,773490,773670,773850,774060,774180,774410,
774690,774774,775320,775390,775698,776490,776910,
777480,778050,778260,778470,778596,779730,779790,
780045,780390,780780,781014,781242,781770,781830,
782340,782782,783090,783510,783870,784740,784770,
785070,785400,785460,785610,785910,786030,786324,
786786,786828,787290,787710,787930,788190,788766,
788970,789222,789360,790020,790230,790482,790790,
791010,791430,791700,792120,792540,792870,793254,
793650,793730,794010,794220,794310,794430,794580,
794640,795340,795522,795795,796110,796290,796620,
796950,797160,797790,797940,798252,798270,798330,
798490,798798,799260,799710,799890,799986,800310,
800394,800730,801570,801780,801990,802230,803010,
803418,803670,803880,803985,804270,804540,804804,
805035,805350,805980,806190,806520,806610,806820,
807534,807576,807690,808080,808170,808830,808860,
808962,809094,809340,809970,810030,810390,810810,
811410,811580,811965,812130,812490,812630,812820,
813450,813540,813960,814506,815100,815430,815490,
816060,816270,816354,816816,817190,817278,817530,
817740,817950,818070,818090,818958,819060,819210,
819390,819546,819910,820050,820410,820820,821100,
821370,821730,821940,822030,822120,822360,822510,
822822,823020,823515,823620,824460,824670,825132,
825330,825630,825930,826098,826210,826770,826980,
827190,827310,827526,827970,828240,828282,828828,
829290,829920,830130,830280,830490,830676,830760,
830830,831390,831402,831810,832260,832370,832524,
832650,832830,833340,833910,834210,834330,834834,
835170,835380,835590,835890,836220,836418,836570,
836940,837210,837330,837930,838110,838695,838860,
838950,839202,839454,839790,840180,840378,840420,
840840,841092,841386,841890,842010,842270,842490,
842520,843030,843150,843180,843570,844305,844998,
845130,845460,845880,845988,846090,846300,846510,
846846,846930,847110,847470,847770,848470,848540,
848562,848820,848946,849030,849090,849870,850080,
850668,850850,851370,851466,851730,852150,852390,
852720,852810,852852,853230,853710,853860,853944,
854490,854700,854910,855270,855855,856086,856254,
856290,857010,857220,857670,857850,858130,858270,
858390,858585,858690,858990,859320,859560,859740,
860370,860430,860574,860860,861042,861630,862290,
862410,862638,862680,863170,863226,863940,864006,
864570,864690,864780,865260,865410,865590,865830,
866580,866910,868020,868140,868434,868530,868560,
868686,869550,869610,869820,870090,870366,870870,
870870,870870,870870,870870,870870,870870,871080,
871332,871530,871794,872340,872508,872610,873642,
873810,874038,874230,874380,874874,875160,875490,
875910,876090,876330,876876,876990,877030,877800,
878010,878220,878370,878430,879060,879270,879450,
879690,879780,880110,880230,880440,880770,881790,
881790,881790,881790,881790,881790,881790,881958,
882420,882570,883190,883740,883890,884070,884442,
884730,885360,885780,885885,886380,886578,886830,
886890,887110,887502,888030,888420,888810,888888,
888930,889140,889746,889770,889980,890010,890274,
890340,890358,890890,891330,891480,891618,891660,
891870,891990,892164,892430,892710,893490,893550,
893970,894102,894660,894894,895356,895440,895620,
896070,896280,896610,897078,897260,897666,898170,
898380,898590,899130,899470,899580,899745,899990,
900354,900900,901170,901320,901740,902190,902538,
903210,903210,903210,903210,903210,903210,903210,
903630,904020,904134,904332,904470,904890,905190,
905730,905970,905982,906360,906510,906780,906870,
906906,907060,907410,907494,907830,908040,908310,
908922,909090,909150,909480,909510,910140,910455,
910470,910860,911064,911430,911820,912030,912450,
912660,912730,912912,913710,913770,913836,914430,
914550,914940,915090,915306,915420,915530,915915,
916370,916674,916734,916860,916980,917070,917490,
917700,917910,918060,918840,918918,919380,919590,
919770,920010,920040,920634,920920,921060,921270,
921570,921690,922350,922530,922845,923286,923780,
923790,923910,924420,924462,924630,925470,925680,
925980,926310,926670,926772,927010,927420,927498,
927960,928200,928290,928620,929292,929390,929670,
930090,930468,930810,930930,930930,930930,930930,
930930,930930,930930,931260,931770,932178,932190,
932790,933240,933570,933660,933702,934206,934230,
934830,935130,935220,935340,936054,936510,936870,
937020,937365,937482,937650,937860,938490,938630,
938730,938910,939120,939246,939510,939930,940170,
940470,940940,941070,941160,941460,941640,941850,
942480,942942,943410,943635,943670,943950,944580,
944790,945438,945516,945630,945714,946050,946110,
946770,947100,947310,947940,948090,948290,948822,
948948,949410,949494,949620,950040,950460,950730,
950820,950950,951258,951405,951510,951720,951762,
952380,952476,952770,953190,953610,953810,954030,
954408,954822,954954,955110,955570,955710,955890,
956046,956130,956340,956670,956760,956802,957030,
957180,957390,958188,958650,959140,959310,959574,
959595,959790,960190,960330,960630,960960,961170,
961350,961590,961620,961818,961860,962220,962598,
963186,963270,963480,963690,963930,964410,964590,
964782,964920,965580,965770,965874,966042,966210,
966420,966570,966810,966966,967470,967890,967980,
968310,968660,968898,969150,969540,969969,969990,
970140,970530,970710,970830,970970,971490,971850,
971880,972230,972510,972660,972762,972930,973182,
973245,973560,973590,973830,973896,974358,974610,
974820,975156,975270,975390,975660,976140,976430,
977130,977262,977340,977730,978054,978120,978180,
978670,978690,978810,978978,979110,979440,980070,
980210,980490,980628,981240,981540,981708,981750,
982410,982770,982905,983010,983535,983710,983892,
984060,984126,984270,984390,984984,985320,985530,
985710,986370,986700,986790,986986,987690,987870,
988218,988260,988494,988680,988890,989430,989520,
990150,990318,990570,990660,990930,990990,991230,
991380,991452,991914,992082,992310,992460,992670,
992940,992970,993174,993300,993510,994290,994422,
994840,994980,995106,995280,995610,995670,996030,
996450,996710,996870,996930,996996,997458,997815,
997890,998070,998580,998634,998760,998844,998970,
999180,999570
};
unsigned int v7[9]={0,510510,570570,690690,746130,
870870,881790,903210,930930};
/*
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<2342&&v6[i]<=x;i++)
if(x==v6[i]) return x;
return v6[i-1];
}
unsigned int cautav7(unsigned int x)
{
unsigned int i;
for(i=0;i<9&&v7[i]<=x;i++)
if(x==v7[i]) return x;
return v7[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==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;*/
cmmn=cautav7(n);break;
default:
{
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;
}
}//switch
}
printf("%u\n",cmmn);
}
return 0;
}
profesor cicalescu nusmaibunkelevi