class Solution(object):

    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        if (n==(int(n**0.5))**2):
            return 1
 
        while((n%4)==0):
            n=n/4
        if ((n%8)==7):
            return 4
				
        for i in xrange(1,int(n**0.5)+1):
            print "here"
            print i
            print n
            print (i*i)
            print int((n-(i**2))**0.5)**2
			
            if (i*i)+int((n-(i**2))**0.5)**2==n:
                return 2

 
        return 3

a=Solution().numSquares(18)
print a

"""
            print "here"
            print i
            print n
            print (n-i*i)
            print (int((n-i*i)**0.5)**2)

"""