#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>

typedef unsigned int uint;

uint *ciur(uint n, uint *size);
uint count_pdivs(uint *cr, uint size, uint n);

int main(void)
{
	FILE *in = fopen("divprim.in", "r");
	FILE *out = fopen("divprim.out", "w");
	if(in != NULL && out != NULL)
	{
		uint size, n, i = 0;
		uint *cr = ciur(1000000, &size);
		fscanf(in, "%u%*c", &n);
		for(; i < n; i++)
		{
			uint a, b;
			fscanf(in, "%u%*c%u%*c", &a, &b);

			int k = a;
			bool found = false;
			while(k >= 2)
			{
				if(count_pdivs(cr, size, k) == b)
				{
					found = true;
					fprintf(out, "%u\n", k);
					break;
				}
				k--;
			}

			if(!found)
			{
				fprintf(out, "0\n");
			}
		}

		fclose(in);
		fclose(out);
	}
	else
	{
		printf("Error\n");
	}

	return 0;
}

uint count_pdivs(uint *cr, uint size, uint n)
{
	uint count = 0, i = 0;
	for(; i < size && n > 1; i++)
	{
		uint p = 0;
		while(n % cr[i] == 0)
		{
			p++;
			n /= cr[i];
		}
		if(p)
		{
			count++;
		}
	}

	return count;
}

uint *ciur(uint n, uint *size)
{
	uint psize = 10, pgrow = 5, pidx = 0;
	uint *primes = malloc(sizeof(uint) * psize);
	uint *vector = calloc(n + 2, sizeof(uint));
	if(primes != NULL && vector != NULL)
	{
		uint i = 2;
		for(; i <= n; i++)
		{
			vector[i] = i;
		}
		primes[pidx++] = 2;
		i = 2;
		for(; i <= n; i += 2)
		{
			vector[i] = 0;
		}

		uint last = 2;
		while(1)
		{
			bool found = false;
			i = last + 1;
			for(; i <= n; i++)
			{
				if(vector[i])
				{
					if((pidx + 1) >= psize)
					{
						psize += pgrow;
						primes = realloc(primes, sizeof(uint) * psize);
						if(primes == NULL)
						{
							printf("Failed to realloc\n");
						}
					}

					primes[pidx++] = i;
					found = true;
					last = i;
					break;
				}
			}

			if(found)
			{
				uint mark = vector[i], inc = i;
				for(; mark <= n; mark += inc)
				{
					vector[mark] = 0;
				}
			}
			else
			{
				break;
			}
		}

		free(vector);
		*size = pidx;
		return primes;
	}
	else
	{
		printf("Failed to init memroy\n");
	}
}