using System;

public class Program

{

    public static void Main()

    {

        int n = 21;

        int highestSq = GetHighestPerfectSquare(n);

        //Console.WriteLine($"highestSq - {highestSq}");

        int m = NumSquares(12);

        Console.WriteLine(m);

    }

    public static int NumSquares(int n) {

        if(IsPerfectSquare(n)){

            return 2;

        }

        int DELTA = 0;

        int Total = 0;

        int highestSq = GetHighestPerfectSquare(n);

        Total = highestSq;

        int nums = 1;

        DELTA = n - highestSq;

        while(true){

            highestSq = GetHighestPerfectSquare(DELTA);

            Total += highestSq;

            nums++;

            if(Total == n){

                return nums;

            }

            DELTA = n - Total;

        }

    }

     public static int GetHighestPerfectSquare(int i){

        if(Math.Sqrt(i)%1 == 0){

            return i;

        }

        else{

            return GetHighestPerfectSquare(--i);

        }

    }

    public static bool IsPerfectSquare(int i){

        return Math.Sqrt(i)%1 == 0;

    }

}