1126. Perfect Squares — Min Number of Squares

Given an integer n, return the least number of perfect square numbers (1, 4, 9, ...) that sum to n. The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the minimum count of perfect squares.

Examples

Example 1

Input: {"n":12}
Output: 3
Explanation: 4 + 4 + 4.

Example 2

Input: {"n":13}
Output: 2
Explanation: 4 + 9.

Example 3

Input: {"n":1}
Output: 1
Explanation: 1 itself.