归纳法，不需要递归，效率最高

#include <stdio.h>

int main(int argc, char *argv[])
{
    int n;

    while (scanf("%d", &n) != EOF) {
        if (1 == n || 2 == n) {
            printf("-1\n");
        } else if (1 == n % 2) {
            printf("2\n");
        } else if (0 == n % 4) {
            printf("3\n");
        } else {
            printf("4\n");
        }
    }

    return 0;
}