#include <bits/stdc++.h>
using namespace std;
const int nx=2e3+5;
struct node
{
int a, b, cur, t, lvl;
node *l, *r, *pa;
node(int a, int b, int cur, int t, int lvl, node* pa): a(a), b(b), cur(cur), t(t), lvl(lvl), l(0), r(0), pa(pa){}
};
typedef node* pnode;
int Q, k, mx=2000, cnt[nx];
pair<int, pnode> res[nx];
pnode rt=new node(1, 1, 0, -1, 0, 0);
queue<pnode> q;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>Q;
for (int i=1; i<=mx; i++) res[i]={(int)1e9, 0};
q.push(rt);
while (!q.empty())
{
auto x=q.front();
q.pop();
cnt[x->cur]++;
res[x->cur]=min(res[x->cur], {x->lvl, x});
if (x->cur+x->a<=mx) q.push(new node(x->a, x->a+x->b, x->cur+x->a, 0, x->lvl+1, x));
if (x->cur+x->b<=mx) q.push(new node(x->a+x->b, x->b, x->cur+x->b, 1, x->lvl+1, x));
}
while (Q--) cin>>k, cout<<cnt[k]<<'\n'<<"-1"<<'\n';
}
