#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

int a[];

int b[];

ll qp(ll x, int y) {

    ll ans = ;

    for(int i=;i<=y;i++) ans*=x;

    return ans;

}

int main()

{

    int t,k=;

    for(int i=;i<=;i++)

    {

        if(b[i]==)

        {

            a[k++]=i;

            for(int j=i+i;j<=;j+=i)

            {

                b[j]=;

            }

        }

    }

    while(~scanf("%d",&t))

    {

        while(t--)

        {

            long long n;

            scanf("%lld",&n);

            int y=powl(n,/5.0);

        //    printf("y:%d\n",y);

            int m=;

            for(int i=;i<k;i++)

            {

            //    printf("%d----\n",a[i]);

                if(a[i]>y)

                break;

                if(n%a[i]==)

                {

                    int r=;

                    while()

                    {

                        if(n%a[i])

                        {

                            break;

                        }

                        n/=a[i];

                        r++;

                    }

                    m=min(m,r);

                }

            }

            //printf("%lld\n",n);

            if(n!=){

            long long y4=powl(n,/4.0);

            long long y3=powl(n,/3.0);

            long long y2=powl(n,/2.0);

            if(qp(y4,)==n||qp(y4+,)==n||qp(y4-,)==n)

            {

                m=min(m,);

             }

             else if(qp(y3,)==n||qp(y3+,)==n||qp(y3-,)==n)

             {

                 m=min(m,);

             }

             else if(qp(y2,)==n||qp(y2+,)==n||qp(y2-,)==n)

             {

                 m=min(m,);

             }

             else

             {

                 m=min(m,);

             }

        }

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

    }

    }

}