Minimum Perfect Squares

You are given a positive integer (n). Your task is to compute the minimum number of perfect square numbers which sum to (n). In other words, find the smallest count of integers (a_1, a_2, \dots, a_k) such that (n = a_1^2 + a_2^2 + \cdots + a_k^2). This problem requires you to determine this count efficiently using techniques such as breadth-first search (BFS) or dynamic programming.

inputFormat

Input is given via standard input (stdin). The input consists of a single line containing a positive integer (n).

outputFormat

Output the minimum number of perfect square numbers that sum to (n) using standard output (stdout).## sample

12

3