namespace GridWits
{
    using System;
    using System.Linq;

    /// <summary>
    /// Class for solving the 'Square Fields' problem.
    /// </summary>
    public class SquareFields
    {
        /// <summary>
        /// Whether to output what is going on during the algorithm.
        /// </summary>
        private readonly bool verbose;

        /// <summary>
        /// The parameter N (number of points) (n in the original code)
        /// </summary>
        private int parameterN; 

        /// <summary>
        /// The parameter K (number of squares required) (kk in the original code)
        /// </summary>
        private int parameterK;

        /// <summary>
        /// The current best found solution (res in the original code)
        /// </summary>
        private int bestFoundSolution;

        /// <summary>
        /// The x coordinates read from the problem (x[100] in the original code)
        /// </summary>
        private int[] xCoordinates;

        /// <summary>
        /// The y coordinates read from the problem (y[100] in the original code)
        /// </summary>
        private int[] yCoordinates;

        /// <summary>
        /// The left bounds for the squares so far (mnx[100] in the original code)
        /// </summary>
        private int[] leftBounds;

        /// <summary>
        /// The left bounds for the squares so far (mxx[100] in the original code)
        /// </summary>
        private int[] rightBounds;

        /// <summary>
        /// The left bounds for the squares so far (mny[100] in the original code)
        /// </summary>
        private int[] lowerBounds;

        /// <summary>
        /// The left bounds for the squares so far (mxy[100] in the original code)
        /// </summary>
        private int[] upperBounds;

        /// <summary>
        /// Initializes a new instance of the <see cref="GridWits.SquareFields"/> class.
        /// </summary>
        /// <param name="verbose">If set to <c>true</c>, be verbose.</param>
        public SquareFields(bool verbose)
        {
            this.verbose = verbose;
        }

        /// <summary>
        /// Goes through all possible partitions recursively, finding the smallest possible size.
        /// We stop the recursion when we have used too many squares or are already bigger than the smallest size we have found so far.
        /// (Rec(i, k, sz) in the original code)
        /// </summary>
        /// <param name="nextPointToPlace">Next point to place. (i in the original code)</param>
        /// <param name="numberOfNonemptySquares">Number of nonempty squares. (k in the original code)</param>
        /// <param name="currentLargestSquareSize">Current largest square size. (sz in the original code)</param>
        private void SolveRecursively(int nextPointToPlace, int numberOfNonemptySquares, int currentLargestSquareSize)
        {
            /* Only continue if the numberOfNonemptySquares is no larger than the final required number of squares
             * and the current size is no larger than the best size found so far
             */
            if (numberOfNonemptySquares <= parameterK && currentLargestSquareSize <= bestFoundSolution)
            {
                // If we have placed all of the points so far, see if our current size improves on the best found solution
                if (nextPointToPlace == parameterN)
                {
                    if (verbose && (bestFoundSolution > currentLargestSquareSize))
                        Console.WriteLine("New solution is an improvement: setting bestFoundSolution to {0}", currentLargestSquareSize);
                    bestFoundSolution = Math.Min(bestFoundSolution, currentLargestSquareSize);
                } 
                else
                {
                    /* Otherwise, we have a new point to place in one of our squares.
                     * Since all of the empty squares are equivalent, we need only try placing our point in any of the nonempty ones 
                     * (index 0 to numberOfNonEmptySquares-1) and the first empty one (index numberOfNonEmptySquares)
                     */
                    for (int squareIndex = 0; squareIndex <= numberOfNonemptySquares; ++squareIndex)
                    {
                        // store the original bounds to return to the original state after we've tried putting the point in this square;
                        int originalLeftBound = leftBounds[squareIndex];
                        int originalRightBound = rightBounds[squareIndex];
                        int originalLowerBound = lowerBounds[squareIndex];
                        int originalUpperBound = upperBounds[squareIndex];

                        // Now put the point in the square
                        leftBounds[squareIndex] = Math.Min(leftBounds[squareIndex], xCoordinates[nextPointToPlace]);
                        rightBounds[squareIndex] = Math.Max(rightBounds[squareIndex], xCoordinates[nextPointToPlace]);
                        lowerBounds[squareIndex] = Math.Min(lowerBounds[squareIndex], yCoordinates[nextPointToPlace]);
                        upperBounds[squareIndex] = Math.Max(upperBounds[squareIndex], yCoordinates[nextPointToPlace]);

                        /* Now recursively attempt to place the next point, incrementing numberOfNonemptySquares if we
                         * placed our point in the first empty one.
                         */
                        int newSizeOfSquare = 
                            Math.Max(rightBounds[squareIndex] - leftBounds[squareIndex], upperBounds[squareIndex] - lowerBounds[squareIndex]);

                        if (verbose)
                        {
                            Console.WriteLine(
                                "Have put point ({0},{1}) in square {2}",
                                xCoordinates[nextPointToPlace],
                                yCoordinates[nextPointToPlace],
                                squareIndex);
                            Console.WriteLine(
                                "Bounds for square {0} are now ({1} to {2}, {3} to {4}), so it is of size at least {5}",
                                squareIndex,
                                leftBounds[squareIndex],
                                rightBounds[squareIndex],
                                lowerBounds[squareIndex],
                                upperBounds[squareIndex],
                                newSizeOfSquare);
                        }

                        SolveRecursively(
                            nextPointToPlace + 1, 
                            Math.Max(numberOfNonemptySquares, squareIndex + 1),
                            Math.Max(currentLargestSquareSize, newSizeOfSquare));

                        if (verbose)
                        {
                            Console.WriteLine(
                                "Backtracking, removing point ({0},{1}) in square {2}",
                                xCoordinates[nextPointToPlace],
                                yCoordinates[nextPointToPlace],
                                squareIndex);
                            newSizeOfSquare = 
                                Math.Max(originalRightBound - originalLeftBound, originalUpperBound - originalLowerBound);
                            if (originalLeftBound < 1000000)
                                Console.WriteLine(
                                    "Bounds for square {0} are now ({1} to {2}, {3} to {4}), so it is of size at least {5}",
                                    squareIndex,
                                    originalLeftBound,
                                    originalRightBound,
                                    originalLowerBound,
                                    originalUpperBound,
                                    newSizeOfSquare);
                            else
                                Console.WriteLine("Square {0} is now empty.", squareIndex);
                        }

                        // now return the bounds of this square to what they were before you put the point in
                        leftBounds[squareIndex] = originalLeftBound;
                        rightBounds[squareIndex] = originalRightBound;
                        lowerBounds[squareIndex] = originalLowerBound;
                        upperBounds[squareIndex] = originalUpperBound;
                    }
                }
            }
        }
            
        /// <summary>
        /// Read the data, run the recursive algorithm and output the answer.
        /// </summary>
        public void Main()
        {
            int numberOfCases = int.Parse(Console.ReadLine());
            for (int caseIndex = 1; caseIndex <= numberOfCases; ++caseIndex)
            {
                int[] parameters = Console.ReadLine().Split(' ').Select(_ => int.Parse(_)).ToArray();
                parameterN = parameters[0];
                parameterK = parameters[1];

                xCoordinates = new int[parameterN];
                yCoordinates = new int[parameterN];
                for (int ptIndex = 0; ptIndex < parameterN; ++ptIndex)
                {
                    int[] coordinates = Console.ReadLine().Split(' ').Select(_ => int.Parse(_)).ToArray();
                    xCoordinates[ptIndex] = coordinates[0];
                    yCoordinates[ptIndex] = coordinates[1];
                }

                leftBounds = new int[parameterK + 1];
                rightBounds = new int[parameterK + 1];
                lowerBounds = new int[parameterK + 1];
                upperBounds = new int[parameterK + 1];
                for (int i = 0; i <= parameterK; ++i)
                {
                    lowerBounds[i] = 1000000; // 64000 would do since the coordinates are supposed to be in the range 0-64000
                    upperBounds[i] = -1000000; // 0 would do since the coordinates are supposed to be in the range 0-64000
                    leftBounds[i] = 1000000; // 64000 would do since the coordinates are supposed to be in the range 0-64000
                    rightBounds[i] = -1000000; // 0 would do since the coordinates are supposed to be in the range 0-64000
                }

                bestFoundSolution = 1000000; // 64000 would do
                SolveRecursively(0, 0, 0);
                Console.WriteLine(@"Case #{0}: {1}", caseIndex, bestFoundSolution);
            }
        }
    }

    /// <summary>
    /// Example solution to Code Jam Problem B
    /// </summary>
    public class CodeJamProblemB
    {
        /// <summary>
        /// The entry point of the program, where the program control starts and ends.
        /// </summary>
        /// <param name="args">The command-line arguments.</param>
        static void Main(string[] args)
        {
            var sf = new SquareFields(false);
            sf.Main();
        }
    }
}