// Program description: http://p...content-available-to-author-only...k.com/cms/?p=449
// Puzzle origin: http://w...content-available-to-author-only...k.com/hackercup/problems.php?pid=191596157517194&round=225705397509134

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Protsyk.Puzzles.Checkpoint {
    class Tuple<T1, T2>
    {
      public T1 Item1 {get; set;}
      public T2 Item2 {get; set;}
      
      public Tuple(T1 item1, T2 item2) { Item1 = item1; Item2 = item2; }
    }

    class Program {

        /// <summary>
        /// Mapping from number N to list of points < (x1, y1), ... >
        /// For each point (x1, y1) in the list of number N following property holds
        /// G(x1, y1) = N, where G(x,y) - is the number of shortest paths from the origin
        /// to (x,y) when only moving right and up is allowed.
        /// </summary>
        static Dictionary<int, List<Tuple<int, int>>> mapping = new Dictionary<int, List<Tuple<int, int>>>();

        static void Main(string[] args) {
            BuildCache();

            int R = int.Parse(Console.ReadLine());
            for (int testcase = 0; testcase < R; testcase++) {
                int S = int.Parse(Console.ReadLine());

                if (S == 1) {
                    Console.WriteLine(string.Format("Case #{0}: {1}", testcase + 1, 2));
                    continue;
                }

                int bestX = int.MaxValue / 2, bestY = int.MaxValue / 2;

                // For each s1,s2 such that s1*s2 = S
                foreach (var factorization in Factorize(S)) {
                    int s1 = factorization.Item1;
                    int s2 = factorization.Item2;

                    // For each grid points for s1
                    foreach (var point1 in GetPointsForNumber(s1)) {
                        // For each grid points for s2
                        foreach (var point2 in GetPointsForNumber(s2)) {

                            // Find best point (with shortest path)
                            if (point1.Item1 + point2.Item1 + point1.Item2 + point2.Item2 < bestX + bestY) {
                                bestX = point1.Item1 + point2.Item1;
                                bestY = point1.Item2 + point2.Item2;
                            }

                        }
                    }
                }

                Console.WriteLine(string.Format("Case #{0}: {1}", testcase + 1, bestX + bestY));
            }
        }

        /// <summary>
        /// Factorize number into two multipliers
        /// </summary>
        static IEnumerable<Tuple<int, int>> Factorize(int s) {
            int s1 = 1;
            int threshold = (int)Math.Sqrt(s) + 1;

            while (s1 <= threshold) {
                int remainder = s % s1;

                if (remainder == 0) {
                    int s2 = s / s1;
                    if (s2 < s1) yield break;
                    yield return new Tuple<int, int>(s1, s2);
                }
                ++s1;
            }
        }

        static Dictionary<int, List<Tuple<int, int>>> BuildCache() {
            List<int> prev = null;
            List<int> next = new List<int>();

            // Start from the second row of the paths matrix G.
            // No need to calculate first and second row, because:
            // G(x,0)=G(0,x)=1
            // G(x,1)=G(1,x)=x+1
            int i = 2;
            int j = 2;

            while (true) {
                while (true) {
                    int number;
                    if (i == j) {
                        if (i == 2)
                            number = 2 * (i + 1); // Use G(x,1)=x+1
                        else
                            number = 2 * prev[1]; // Use previous row
                    } else {
                        if (i == 2)
                            number = next[j - i - 1] + (j + 1); // Use G(x,1)=x+1
                        else
                            number = next[j - i - 1] + prev[j - i + 1]; // Use previous row
                    }

                    // Task threshold
                    if (number > 10000000)
                        break;

                    List<Tuple<int, int>> pointslist = new List<Tuple<int, int>>();
                    if (!mapping.TryGetValue(number, out pointslist)) {
                        pointslist = new List<Tuple<int, int>>();
                        pointslist.Add(new Tuple<int, int>(number - 1, 1));
                        mapping.Add(number, pointslist);
                    }
                    pointslist.Add(new Tuple<int, int>(i, j));

                    next.Add(number);
                    ++j;
                }

                if (next.Count < 2) {
                    // Only one number, break
                    break;
                } else {
                    prev = next;
                    next = new List<int>(next.Count + 1);
                }

                ++i;
                j = i;
            }
            return mapping;
        }

        /// <summary>
        /// Get points from the cache
        /// </summary>
        static IEnumerable<Tuple<int, int>> GetPointsForNumber(int s) {
            if (s == 1) {
                // Return point closest to origin
                yield return new Tuple<int, int>(1, 0);
                yield break;
            }

            List<Tuple<int, int>> result;
            if (mapping.TryGetValue(s, out result)) {
                foreach (Tuple<int, int> point in result)
                    yield return point;
            } else {
                // There is only one point for such number,
                // it is in the first row of the matrix
                yield return new Tuple<int, int>(s - 1, 1);
            }
        }

    }
}