Minimum Perfect Squares

Given an integer \(N\) (where \(N \geq 0\)), determine the minimum number of perfect squares that sum up to \(N\). A perfect square is a number of the form \(k^2\) where \(k\) is a positive integer. For example, when \(N=12\), the answer is 3 since \(12=4+4+4\), and when \(N=13\), the answer is 2 because \(13=4+9\).

inputFormat

The input consists of a single integer \(N\) read from stdin.

outputFormat

Output a single integer representing the minimum number of perfect squares that sum up to \(N\). The result should be printed to stdout.

12

3