C

#include <bits/stdc++.h>

using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)

int main()
{
    int N = 1e6 + 1;
    vector<int> isPrime(N, 1);

    isPrime[1] = 0;

    for(int i=2; i<N; i++)
    {
        if(!isPrime[i])     continue;

        for(int j=2*i; j<N; j+=i)
            isPrime[j] = 0;
    }

    _test
    {
        int n;
        cin>>n;

        int curr = 1;
        int ans = 0;

        while(n > 0)
        {
            ans++;
            if(isPrime[n])
            {
                n = 0;
                break;
            }

            n -= curr;
            curr *= 2;
        }

        if(n == 0)      cout<<ans<<"\n";
        else            cout<<-1<<"\n";
    }
}