1#include <bits/stdc++.h>
 2#define PB push_back
 3#define fst first
 4#define sec second
 5#define lson l,m,rt<<1
 6#define rson m+1,r,rt<<1|1
 7#define ms(a,x) memset(a,x,sizeof(a))
 8typedef long long LL;
 9#define pi pair < int ,int >
10#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6#define MAXALP 30
 7struct state
 8{
 9    int len, link, nxt[MAXALP];
10    int leftmost; //由于要求出现位置最小的，leftmost表示第一次出现的右端点位置。
11};
12const int N =1E5+7;
13state st[N*2];
14int sz, last,rt;
15char s[N];
16int cnt[2*N],rk[2*N];//for radix sort
17void sa_init()
18{
19    sz = 0;
20    last = rt = ++sz;
21    st[1].len = 0;
22    st[1].link=-1;
23    ms(st[1].nxt,-1);
24}
25void sa_extend(int c,int head)
26{
27    int cur = ++sz;
28    st[cur].len = st[last].len + 1;
29    st[cur].leftmost = head;
30    memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
31    int p;
32    for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
33        st[p].nxt[c] = cur;
34    if (p == -1) {
35        st[cur].link = rt;
36    } else {
37        int q = st[p].nxt[c];
38        if (st[p].len + 1 == st[q].len) {
39            st[cur].link = q;
40        } else {
41            int clone = ++sz ;
42            st[clone].len = st[p].len + 1;
43            st[clone].link = st[q].link;
44            memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
45            st[clone].leftmost = st[q].leftmost;
46            for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
47                st[p].nxt[c] = clone;
48            st[q].link = st[cur].link = clone;
49        }
50    }
51    last = cur;
52}
53void topo()
54{
55    ms(cnt,0); 
56    for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
57    for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
58    for (int i = 1 ; i <= sz  ;i++) rk[cnt[st[i].len]--] = i;
59}
60string S;
61void solve (string S)
62{
63    sa_init();
64    int n = S.length();
65    int i = 0 ;
66    while (i<n)
67    {
68    int now = rt;
69    int len = 0 ;
70    while (i<n &&st[now].nxt[S[i]-'a']!=-1)
71    {
72        now = st[now].nxt[S[i]-'a'];
73        len++;
74        sa_extend(S[i]-'a',i);
75        i++;
76    }
77    if (!len)
78    {
79        sa_extend(S[i]-'a',i);
80        printf("%d %d\n",-1,S[i]);
81        i++;
82    }
83    else printf("%d %d\n",len,st[now].leftmost-len+1);
84    }
85}

1int main()
2{
3#ifndef  ONLINE_JUDGE 
4        freopen("./in.txt","r",stdin);
5#endif

1    int T;
2    int cas = 0 ;
3    cin>>T;
4    while (T--)
5    {
6        printf("Case #%d:\n",++cas);
7        cin>>S;
8        solve(S);
9    }

1#ifndef ONLINE_JUDGE  
2    fclose(stdin);
3#endif
4    return 0;
5}