#include<cstdio>
using namespace std;
#define MAX_N 1000000
int a[10][MAX_N+15];
char ciur[MAX_N+15];
void ciuruire() {
	int i, j;
	for(i=2;i*i<=MAX_N;) {
		for(j=2;j*i<=MAX_N;j++)
			ciur[i*j]++;
		while(ciur[++i]!=0){}
	}
	for(i=2;i<=MAX_N;i++) {
		if(ciur[i]==0)ciur[i]=1;
		a[1][i]=a[1][i-1];
		a[2][i]=a[2][i-1];
		a[3][i]=a[3][i-1];
		a[4][i]=a[4][i-1];
		a[5][i]=a[5][i-1];
		a[6][i]=a[6][i-1];
		a[7][i]=a[7][i-1];
		a[ciur[i]][i]=i;
	}
}
int main() {
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int  t;
	scanf("%d",&t);
 	ciuruire();
	while(t-->0) {
		int n, k;
		scanf("%d%d",&n,&k);
		if(k==0)
			printf("1\n");
		else
			printf("%d\n",a[k][n]);
	}
	return 0;
}