#include <bits/stdc++.h>

 #define LL long long

 #define lowbit(x) x&(-x)

 #define inf 2e18

 using namespace std;

 inline LL ra()

 {

     LL x=,f=; char ch=getchar();

     while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

     while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

     return x*f;

 }

 LL f[],n;

 int top,P;

 map<LL, int > F;

 int solve(LL x)

 {

     if (F[x]) return F[x];

     int t=lower_bound(f,f+top,x)-f;

     if (f[t]==x) return ;

     return F[x]=min(solve(x-f[t-]),solve(f[t]-x))+;

 }

 int main()

 {

     f[]=; f[]=;

     for (int i=; f[i-]<=inf; i++,top++) f[i]=f[i-]+f[i-];

     P=ra();

     for (int i=; i<=P; i++)

         printf("%d\n",solve(ra()));

     return ;

 }