#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

ll gcd(ll a, ll b){return (b==0?a:gcd(b,a%b));}

ll modlog(ll a, ll b, ll p){
  ll g=1;
  for(ll i=p; i>0; i/=2){
    g *= a;
    g %= p;
  }
  g = gcd(g,p);
  ll t=1,c=0;
  while(t%g>0){
    if(t==b) return c;
    t *= a;
    t %= p;
    c++;
  }
  if(b%g > 0) return -1;

  t/=g;
  b/=g;

  ll n=p/g,h=0,gs=1;
  for(;h*h<n;h++){
    gs *= a;
    gs %= n;
  }
  unordered_map<ll,ll> bs;
  for(ll s=0,e=b;s<h;bs[e]=++s){
    e *= a;
    e %= n;
  }
  for(ll s=0,e=t;s<n;){
    e*=gs;
    e%=n;
    s+=h;
    if(bs.count(e) > 0) return c+s-bs[e];
  }
  return -1;
}

ll solve(ll N){
  if(N == 1) return 1;
  return modlog(2,1,2*N+1);
  
  vector<int> v;
  rep(i,2*N) v.push_back(i+1);

  rep(i,1000){
    //rep(j,v.size()) cout << v[j] << " "; cout << endl;    
    vector<int> w(v.size());
    rep(j,N){
      w[2*j] = v[j];
      w[2*j+1] = v[N+j];
    }
    swap(v, w);

    bool flg = true;
    rep(j,v.size()) if(j+1 != v[j]) flg = false;
    if(flg) return i+1;
  }
  
  return -1;
}

int main(){
  int T;
  cin >> T;

  rep(t,T){
    ll N;
    cin >> N;
    cout << solve(N) << endl;
  }
  
  return 0;
}