CUBEFR.cpp

#include<stdio.h>

const int MAX = 1000001;
int free_cube[MAX];

void create_free_cube()
{
	for(int i = 2; i <= 100; i++)
	{
		int t = i*i*i;
		int j = 1;

		while(true)
		{
			int temp = t*j;
			if(temp < MAX)
			{
				free_cube[temp] = -1;
				j++;
			}
			else break; 
		}
	}

	int cnt = 0;
	for(int i = 1; i < MAX; i++)
		if(free_cube[i] > -1) 
		{
			cnt++;
			free_cube[i] = cnt;
		}
}

int main()
{
	int T = 0;
	scanf("%d",&T);

	for(int i = 0; i < MAX; i++) 
	    free_cube[i] = 0;
	    
	create_free_cube();

	for(int tc = 0; tc < T; tc++)
	{
		int n = 0;
		scanf("%d",&n);

		if(free_cube[n] == -1) printf("Case %d: Not Cube Free\n",tc+1);
		else printf("Case %d: %d\n",tc+1,free_cube[n]);
	}
	return 0;
}