#include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll f[],n,m;

 inline ll read(){

     ll f=,x=;char ch;

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

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

     return f*x;

 }

 int work(ll x){

     if(!x)return x;int i;

     for(i=;f[i]<x;i++);

     return work(min(f[i]-x,x-f[i-]))+;

 }

 int main(){

     f[]=;f[]=;

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

     int T=read();

     while(T--){

         n=read();

         printf("%d\n",work(n));

     }

     return ;

 }