import?java.util.Scanner;
public?class?Main?{
//用於存放已經計算過的Method(n),提高計算速度
static?int?data[]=new?int[100000001];
public?static?void?main(String?args[]){
int?n=new?Scanner(System.in).nextInt();
System.out.println(Method(n));
}
static?int?Method(int?n){
//如果n是完全平方數，返回結果?只需壹次?遞歸出口
if(Math.pow((int)Math.sqrt(n),2)==n){
return?1;
}else{
if(data[n]!=0){
return?data[n];
}
//窮舉?如果13，就窮舉1+12?2+11?……
//當執行f(1)+f(12)時
//f(1)=1,?f(12)再執行窮舉，依次類推
//最終得出最少次數，比如f(4)+f(9)=2,即為最終結果.
int?min=Method(n-1)+Method(1);
for(int?i=1;i<=n/2;i++){
if(Method(i)+Method(n-i)<min){
min=Method(i)+Method(n-i);
}
}
data[n]=min;
return?min;
}
}
}