#include<iostream>
#include<cstring>
using namespace std;
const int N=10010;
int n,m;
int v[N],w[N],f[N];
int main(){
cin>>n;
int ans=1;
while(n--){
cin>>m;
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=100;i++)// for(int i=1;i*i<=m;i++)
for(int j=i*i;j<=m;j++)
f[j]=min(f[j],f[j-i*i]+1);
cout<<"Case #"<<ans<<": "<<f[m]<<endl;
ans++;
}
return 0;
}