题目描述

世上最远的距离不是千山万水，而是你我间相隔一个维度。

给定正整数 $n$，求最小的正整数 $k$，使存在 $k$ 个正整数 $x_1 \dots x_k$ 满足 $x_1^2 + x_2^2 + \dots + x_k^2=n$

输入格式

仅一个整数 $n$。

输出格式

一个整数表示答案。

输入输出样例

输入样例1

14

输出样例1

3

输入样例2

15

$14 = 1^2 + 2^2 + 3^2$，而不存在 $2$ 个正整数的平方和等于 $14$。

输出样例2

4

数据范围与提示

对于 $10\%$ 的数据，$n \le 10$； 对于 $50\%$ 的数据，$n \le 100$; 对于 $100\%$ 的数据，$n \le 100000$。