#include<cstdio>

 #include<algorithm>

 #define ll long long

 #define mid (l+r>>1)

 using namespace std;

 ll f[],tot=;

 inline ll findl(ll x)

 {

     int l=,r=tot,ans=;

     while(l<=r)

     {

         if(f[mid]<=x)ans=mid,l=mid+;

         else r=mid-;

     }

     return f[ans];

 }

 inline ll findr(ll x)

 {

     int l=,r=tot,ans=;

     while(l<=r)

     {

         if(f[mid]>=x)ans=mid,r=mid-;

         else l=mid+;

     }

     return f[ans];

 }

 int solve(ll x)

 {

     ll l=findl(x),r=findr(x);

     if(l==r)return ;

     if(x-l<=r-x)return solve(x-l)+;

     return solve(r-x)+;

 }

 int main()

 {

     f[]=f[]=;

     while(f[tot-]<=4e17)

     f[++tot]=f[tot-]+f[tot-];

     int t;scanf("%d",&t);

     ll x;

     while(t--)scanf("%lld",&x),

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

 }