#include <cstdio>
#include <cmath>

int countFactors(int fator, int num)
{
	int quantidade = 0;
	while (num % fator == 0)
	{
		quantidade++;
		num = num / fator;
	}
	return quantidade;
}

int checkPrimo(int primo)
{
	if (primo == 2 || primo == 3 || primo == 5)
		return 1;
	if (primo%2 == 0)
		return 0;
	if (primo % 3 == 0)
		return 0;
	if (primo % 5 == 0)
		return 0;

	int i;
	int max = round(sqrt(primo));
	for (i = 1; (6*i+5) <= max; i++)
	{
		if (primo % (6*i + 1) == 0 || primo % (6*i + 5) == 0)
		{
			return 0;
		}
	}
	return 1;
}

int main()
{
	int t;
	scanf("%d", &t);
	int i;
	for (i = 0; i < t; i++)
	{
		long long int num;
		scanf("%lld", &num);
		if (checkPrimo(num))
		{
			printf("Caso #%d: %d\n",i+1, num*num);
			continue;
		}
		int fator;
		for (fator = 2; fator < num; fator++)
		{
			if (checkPrimo(fator))
			{
				if (countFactors(fator, num) % 2 == 1)
					num = num * fator;
			}
		}
		printf("Caso #%d: %lld\n", i+1, num);
	}
}