#include<fstream>
using namespace std;
short v[502];
long long nr,st,rez;
ifstream in("doi.in");
ofstream out("doi.out");
int min(int a,int b) {if(a>b) return b;return a;}
void citeste()
{char c;
c=in.get();
nr=0;
while(c!=10)
	{v[nr]=c-48;
	nr++;
	c=in.get();	
	}
}
void merita()
{int n,i,j;
long long k=0;
n=min(16,nr-st);
for(i=nr-n;i<nr;i++)
	k=k*10+v[i];
k++;
for(i=2;k%i==0&&i<k;)
	i*=2;
k-=2;
for(j=2;k%j==0&&j<k;j*=2);
if(i>j&&i>=8)
	{v[nr-1]++;
	i=nr-1;
	while(v[i]>9)
		v[i-1]+=v[i]/10,v[i]%=10,i--;
	}
else
	{v[nr-1]--;
	i=nr-1;
	while(v[i]<0)	
		v[i]+=10,v[i-1]--,i--;
	}
}
void imparte(int p)
{int i,r=0;
for(i=0;i<nr;i++)
	{r=r*10+v[i];
	v[i]=r/p;
	r%=p;
	}
for(;v[st]==0;st++);
}
void divide()
{int n,p,k=0,i;
n=min(10,nr-st);
p=1<<n;
for(i=nr-n;i<nr;i++)
	k=k*10+v[i];
while(k%p!=0)
	p/=2,n--;
rez+=n;
imparte(p);
}
void make()
{st=0;rez=0;
while(st<=nr-1)
	{if(st==nr-1&&v[st]==1)
		{rez++;
		break;}
	if(v[nr-1]%2==0)
		divide();
	else
	{rez++;
	merita();}
	}
out<<rez<<'\n';	
}
int main()
{short i,t;
in>>t;in.get();
for(i=0;i<t;i++)
	{citeste();
	make();
	}
in.close();
out.close();
return 0;	
}