Period

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+5;
typedef long long ll;
ll nxt[N]; 
struct stu{
    ll a,b;
    bool friend operator <(const stu &x,const stu &y){
        if(x.a!=y.a) return x.a<y.a;
    }
}arr[N];

int main(){
    int t,k=0;
    while(~scanf("%d",&t)!=EOF,t){
        memset(nxt,0,sizeof(nxt));
        k++;
        string a;
        cin>>a; 
        for(int i=1;i<a.size();i++){
            int j=nxt[i-1];
            while(j>0&&a[i]!=a[j]) j=nxt[j-1];
            if(a[i]==a[j]) j++;
            nxt[i]=j;
        } 
        ll pos=0; 
        printf("Test case #%d\n",k); 
        
        for(int i=1;i<a.size();i++) {
            int j=i+1;//总长度，
            // j%(j-nxt[i])用来判断j-nxt[i]是否可以作为该段的最小循环长度，
            // j/(j-nxt[i]) 循环周期 
            if(j%(j-nxt[i])==0 && j/(j-nxt[i])>=2){ 
                arr[pos].a=j;
                arr[pos++].b=j/(j-nxt[i]); 
            }
        } 
         sort(arr,arr+pos);
         for(int i=0;i<pos;i++){
             cout<<arr[i].a<<" "<<arr[i].b<<endl;
         }
         cout<<endl;
    }
    return 0;
}