Minimum Perfect Squares Sum

Given a positive integer \( n \), split it into the sum of one or more perfect squares. In other words, find the minimum number \( k \) such that:

\( n = a_1^2 + a_2^2 + \cdots + a_k^2 \)

Your task is to compute and output \( k \).

inputFormat

The input consists of a single positive integer \( n \).

outputFormat

Output a single integer representing the minimum number of perfect squares that sum up to \( n \).

sample

12

3