#include<iostream>
#include<string.h>
#include<fstream>

using namespace std;
long long sol=0,s=0;
int nr;
int A[600],b[2]={1,1};
void imparte(int A[600], long long X)
{ 
	int i;
	long long R=0;
	for (i=A[0];i;i--)
    { 
	  A[i]=(R=10*R+A[i])/X;
      R%=X;
    }
  while (!A[A[0]] && A[0]>1) A[0]--;
  
}


void aduna(int a[1000],int b[1000])
{
	int i,minte=0;
	if (b[0]>a[0]){
		for (i=a[0]+1;i<=b[0];)
			a[i++]=0;
		a[0]=b[0];
	}
	else
		for (i=b[0]+1;i<=a[0];)
			b[i++]=0;
	for (i=1;i<=a[0];i++)
	{
		a[i]=a[i]+b[i]+minte;
		minte=a[i]/10;
		a[i]=a[i]%10;
	}
	if (minte)
		a[++a[0]]=minte;
}
void  scade(int a[1000], int b[1000])
{
	
	int i,minte=0;
	for (i=b[0]+1;i<=a[0];i++)
		b[i]=0;
	for (i=1;i<=a[0];i++)
	{
		a[i]=a[i]-b[i]-minte;
		if (a[i]<0)
			minte=1;
		else
			minte=0;
		if (minte)
			a[i]=a[i]+10;
	}
	 while (!a[a[0]] && a[0]>1) a[0]--;
}
int rezolva (long long nr)
{
	nr=10*A[2]+A[1];
	if (nr==0 && A[0]==1)
			return sol;
	else
		if (nr%2==0)
		{
			imparte(A,2);
			sol++;
			rezolva(nr);
		}
		else
			if (nr%4==1 || nr==3)
				{	
					
					scade (A,b);
					sol++;
					rezolva(nr);
			}
			else
				if (nr%4==3|| nr==3)
				{
					aduna(A,b);
					sol++;
					rezolva(nr);
				}
				
			
			
}

	
int main(void)
{

	int t;
	char lin[1000];
	fstream f,g;
	f.open("doi.in",ios::in);
	g.open("doi.out",ios::out);
	f>>t;
	f.get();
	while (t--)
	{
		f.getline(lin,1000);
		int n=0,i;
		for(i=strlen(lin)-1;i>=0;i--)
			A[++n]=lin[i]-48;
		A[0]=n;
		nr=10*A[2]+A[1];
		rezolva(nr);
		g<<sol<<"\n";
		sol=0;
		s=0;
	}
}