Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer (e.g., 1, 4, 9, 16, ...).

Example 1:

Input: n = 12
Output: 3 (12 = 4 + 4 + 4)

Example 2:

Input: n = 13
Output: 2 (13 = 4 + 9)

Constraints: 1 <= n <= 10^4