#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void getp(long long N,long long*prim);
unsigned long long modPow(unsigned long long a,unsigned long long x,unsigned long long mod);
long long get_phi(long long N,long long *prime);
void solve(int count,int* c,int* rp,long long pp,long long x);
long long bigmm(long long a,long long b,long long mod);
long long a;

int main(){
  int T,count,*rp,*c,i,j;
  long long x,b,*p,*lcd,P,lcm;
  rp=(int*)malloc(80*sizeof(int));
  c=(int*)malloc(80*sizeof(int));
  p=(long long*)malloc(1000000*sizeof(long long));
  lcd=(long long*)malloc(80*sizeof(long long));
  getp(1000000,p);
  scanf("%d",&T);
  while(T--){
    a=((long long)1)<<60;
    scanf("%lld",&x);
    b=0;
    if(x%2==0)
      x/=2;
    if(x%2==0)
      x/=2;
    while(x%10==0){
      b++;
      x/=10;
    }
    while(x%2==0){
      b++;
      x/=2;
    }
    while(x%5==0){
      b++;
      x/=5;
    }
    count=0;
    lcm=x;
    x=get_phi(9*x,p);
    for(i=0;p[i];i++)
      if(x%p[i]==0){
        rp[count]=p[i];
        c[count]=0;
        while(x%p[i]==0){
          x/=p[i];
          c[count]++;
        }
        count++;
      }
    if(x!=1){
      rp[count]=x;
      c[count]=1;
      count++;
    }
    solve(count,c,rp,1,lcm*9);
    printf("%lld\n",2*a+b);
  }
  return 0;
}
void getp(long long N,long long*prim){
  long long i,j,index=2,flag;
  if(N<=1){
    prim[0]=0;
    return;}
  if(N==2){
  prim[0]=2;
  prim[1]=0;
  return;}
  prim[0]=2;
  prim[1]=3;
  for(i=5;i<=N;i=i+2)
    {
      for(j=1,flag=1;prim[j]<=sqrt(i);j++)
        {
          if(i%prim[j]==0){
            flag=0;
            break;}
        }
      if(flag==1)
        {prim[index]=i;
          index++;}
    }
  prim[index]=0;
  return;
}
unsigned long long modPow(unsigned long long a,unsigned long long x,unsigned long long mod){
  unsigned long long res = 1;
  while(x>0){
    if(x%2)
      res=bigmm(a,res,mod);
    a=bigmm(a,a,mod);
    x>>=1;
  }
  return res;
}
long long get_phi(long long N,long long *prime){
  long long ans=N,i;
  for(i=0;prime[i]*prime[i]<=N && prime[i];i++)
    if(N%prime[i]==0){
      while(N%prime[i]==0)
        N/=prime[i] ;
      ans=ans-ans/prime[i];
    }
  if(N>1)
    ans=ans/N*(N-1);
  return ans;
}
void solve(int count,int* c,int* rp,long long pp,long long x){
  int i;
  if(count==0){
    if(modPow(10,pp,x)==1 && pp<a)
      a=pp;
    return;
  }
  solve(count-1,c+1,rp+1,pp,x);
  for(i=0;i<c[0];i++){
    pp*=rp[0];
    solve(count-1,c+1,rp+1,pp,x);
  }
  return;
}
long long bigmm(long long a,long long b,long long mod){
  int ar[20],size=0,i,j;
  long long ans=0,temp;
  for(i=0;b;i++){
    ar[i]=b%10;
    size++;
    b/=10;
  }
  for(i=0;i<size;i++){
    temp=ar[i]*a%mod;
    for(j=0;j<i;j++)
      temp=temp*10%mod;
    ans=(ans+temp)%mod;
  }
  return ans;
}