SPOJ PERIOD

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

const int OO = 1e9;
const double EPS = 1e-9;

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for(int ti = 1; ti <= t; ti++) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> f(s.length());
        cout << "Test case #" << ti << "\n";
        for(int i = 1, k = 0; i < s.length(); i++) {
            while(k > 0 && s[k] != s[i]) {
                k = f[k-1];
            }
            f[i] = (s[i] == s[k] ? ++k:k);
            //cout << "f[" << i << "] = " << f[i] << "\n";
            if(f[i]*2 >= i+1 && !((i+1)%(i+1 - f[i]))) {
                cout << i+1 << " " << (i+1)/(i+1 - f[i]) << "\n";
            }
        }
        cout << "\n";
    }
    return 0;
}