描述

我们可爱的 c小加 近段儿正在潜心研究数学,当他学习到循环小数这一部分时不是太明白循环体是什么意思(比如说3.23232323的循环体是23、2323、23232323),假设我们现在的循环小数都是严格循环的并且有限的,也就是说不出现2.16666666(循环体为6,长度为1)的情况,只有123123这样的循环出现。给他一个小数,他需要找出最小循环体的长度、循环体和循环的次数,请你帮他解决这个问题。

输入

输入的第一行是t,表示有t组测试数据(t<=100)。 
随后的t行,每行都是一个小于10并且大于0的小数(总长度<=200)。

输出

对每组输入,输出结果单独成行,输出最小循环体的长度、循环体和出现循环的次数。

样例输入


8.6987698769876987 
0.666 
5.1

样例输出

4 6987 4 
1 6 3 
1 1 1

#include<stdio.h>
#include<string.h>
char a[222],s[222];
int next[222];
int len,c;
void getnext()
{
    int i=0,j=-1;       //s[j]为循环的开始,s[i]为下一个循环的开始;
    next[i]=j;
    while(i<len)
    {
        if(j==-1||s[i]==s[j])
        {
            i++,j++;
            next[i]= j;
        }
        else
        j = next[j];
    }
    if(len%(len-next[len])==0)
        c=len/(i-j);//循环次数
}
int main()
{
    int t,l,i,j;
    scanf("%d",&t);
    while(t--)
    {
        memset(s,'\0',sizeof(s));
        scanf("%s",a);
        len=strlen(a);
        for(i=2,j=0;i<len;i++,j++)
            s[j] = a[i];
        len-=2;
        getnext();
        l=len/c; //循环节长度
        printf("%d ",l);
        for(i=0;i<l;i++)
        printf("%c",s[i]);//循环节
        printf(" %d\n",c); //次数
    }
    return 0;
}