原数给的范围太大了，直接找规律：除了1、2行，奇数行必定是每行第2个数为偶数，当行数为4的倍数时每行的第3个数为偶数，只为2的倍数时每行的第4个数为偶数。 
#include <iostream>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n==1 || n==2){
            cout << "-1";
        }
        else if(n%2==1){
            cout << "2";
        }
        else if(n%4==0){
            cout << "3";
        }
        else cout << "4";
    }
}