import java.util.Scanner; import java.util.HashSet; import java.util.ArrayList; public class Main { static int solve(int n) { HashSet exists = new HashSet<>(); ArrayList ts = new ArrayList<>(); for (int t, i = 1; (t = i * (i + 1) / 2) <= n; i++) { if (t == n) { return 1; } ts.add(t); exists.add(t); } for (int t : ts) { if (exists.contains(n - t)) { return 2; } } return 3; } public static void main(String... argv) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(solve(n)); } }