【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;
int ne[maxn];
int cnt;

void getNext(string t) {
    int len=t.length();
    int i=0, j=-1;
    ne[0]=-1;
    while(i<len) {
        if(j==-1 || t[i]==t[j]) {
            ne[++i]=++j;
        } else j=ne[j];
    }
}

int main() {
    string s;
    int n;
    while(cin>>n) {
        if(n==0) break;
        cin>>s;
        cnt++;
        cout<<"Test case #"<<cnt<<endl;
        getNext(s);
        for(int i=2; i<=n; i++) {
            if(i%(i-ne[i])==0 && i/(i-ne[i])>1) {
                cout<<i<<" "<<i/(i-ne[i])<<endl;
            }
        }
        cout<<endl;
    }

    return 0;
}

/*
in:
3
aaa
4
abcd
12
aabaabaabaab
0

out:
Test case #1
2 2
3 3

Test case #2

Test case #3
2 2
6 2
9 3
12 4
*/