package dp;

import java.util.Arrays;
import java.util.Scanner;

public class 吃蛋糕完全背包问题 {

    /**
     * 这个题目用完全背包求解最小值问题
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
      Scanner scanner = new Scanner(System.in);
      int t=scanner.nextInt();
      int c=1;
      while(t>0){
          t--;
          int k=scanner.nextInt();
          int to=(int) (Math.sqrt(k)+1);
          int f[][]=new int[k][k+1];
          for(int i=0;i<k;i++)Arrays.fill(f[i], Integer.MAX_VALUE);

          f[0][0]=0;
          //从0个物品里面选择0个商品的方案数目是0

          for(int i=1;i<=to;i++){
              for(int j=0;j<=k;j++){
                  f[i][j]=f[i-1][j];
                  if(j>=i*i){
                      f[i][j]=Math.min(f[i][j], f[i][j-i*i]+1);
                  }
              }
          }
          System.out.println("Case #"+c+": "+f[to][k]);
          c++;
      }
    }

}