#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100005

using namespace std;

char s[maxn*];

int next[maxn];

void kmp(int n)

{

    int j=;

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

    {

        while(j>&&s[i]!=s[j+])j=next[j];

        if(s[i]==s[j+])++j;

        next[i]=j;

    }

}

void MinimumRepresentation(int n)

{

    int i=,j=,k=;

    while()

    {

        if(i==j)j++;

        else if(s[j]=='')j++;

        else if(s[i]=='')i++;

        else if(s[i+k]==s[j+k])k++;

        else if(s[i+k]<s[j+k])

        {

            if(s[i+k]=='')j=j+k;

            else j=j+k+;

            k=;

        }

        else

        {

            if(s[j+k]=='')i=i+k;

            else i=i+k+;

            k=;

        }

        if(i>n||j>n||k>=n) break;

    }

    int t=i<=n?i:j;

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

        putchar(s[i]);

    puts("");

}

int main()

{

    //freopen("test0.in","r",stdin);

    int t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%s",s+);

        n=strlen(s+);

        bool flag=;

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

            if(s[i]!='')flag=;

        if(flag==){printf("1%s\n",s+);continue;}

        kmp(n);

        int m=n-next[n];

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

            s[i]=s[i-m];

        MinimumRepresentation(m);

    }

    return ;

}