import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] dp = new int[n + 1];
 
        // 初始化dp数组，最坏情况是全部由1组成，个数为n
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 初始化为最大值（全1）
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
 
        System.out.println(dp[n]);
        scanner.close();
    }
}

aW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwoKcHVibGljIGNsYXNzIE1haW4gewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIFNjYW5uZXIgc2Nhbm5lciA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbik7CiAgICAgICAgaW50IG4gPSBzY2FubmVyLm5leHRJbnQoKTsKICAgICAgICBpbnRbXSBkcCA9IG5ldyBpbnRbbiArIDFdOwogICAgICAgIAogICAgICAgIC8vIOWIneWni+WMlmRw5pWw57uE77yM5pyA5Z2P5oOF5Ya15piv5YWo6YOo55SxMee7hOaIkO+8jOS4quaVsOS4um4KICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICAgICAgZHBbaV0gPSBpOyAvLyDliJ3lp4vljJbkuLrmnIDlpKflgLzvvIjlhagx77yJCiAgICAgICAgICAgIGZvciAoaW50IGogPSAxOyBqICogaiA8PSBpOyBqKyspIHsKICAgICAgICAgICAgICAgIGRwW2ldID0gTWF0aC5taW4oZHBbaV0sIGRwW2kgLSBqICogal0gKyAxKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oZHBbbl0pOwogICAgICAgIHNjYW5uZXIuY2xvc2UoKTsKICAgIH0KfQ==

OQ==

9