C++ :

#include <bits/stdc++.h>
using namespace std;
inline bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2; i*i <= n; i++) if(n % i == 0) return false;
    return true;
}
int t, n;
bool flag;
int main(){
    scanf("%d", &t);
    while(t--){
        flag = false;
        scanf("%d", &n);
        for(int i = 0, now = 0; now <= n; ++i, now = now<<1 | 1){
            if(n - now <= 0){
                printf("%d\n", i);
                goto next;
            }
            else if(is_prime(n-now)){
                printf("%d\n", i+1);
                goto next;
            }
        }
        puts("-1");
        next:;
    }
}