from math import sqrt
def numSquares(n):
 if n <= 0:
 return 0
 legal_nums = [e**2 for e in range(1, int(sqrt(n)) + 1)]
 layers = 0
 current_queue = {n}
 while current_queue:
 layers+=1
 next_queue = set()
 for elem in current_queue:
 for legal_num in legal_nums:
 if elem == legal_num:
 return layers
 elif elem<legal_num:
 break
 else:
 next_queue.add(elem-legal_num)
 current_queue = next_queue
 return layers

def main():
 n = 12
 # print(numSquares(0))
 print(numSquares(7168))
 print(numSquares(n))
if __name__ == "__main__":
 main()