1/* ***********************************************
  2Author :111qqz
  3Created Time :2017年11月08日 星期三 18时50分18秒
  4File Name :4436.cpp
  5************************************************ */
  6
  7#include <bits/stdc++.h>
  8#define PB push_back
  9#define fst first
 10#define sec second
 11#define lson l,m,rt<<1
 12#define rson m+1,r,rt<<1|1
 13#define ms(a,x) memset(a,x,sizeof(a))
 14typedef long long LL;
 15#define pi pair < int ,int >
 16#define MP make_pair
 17
 18using namespace std;
 19const double eps = 1E-8;
 20const int dx4[4]={1,0,0,-1};
 21const int dy4[4]={0,-1,1,0};
 22const int inf = 0x3f3f3f3f;
 23#define MAXALP 30
 24struct state
 25{
 26    int len, link, nxt[MAXALP];
 27    int leftmost; //由于要求出现位置最小的，leftmost表示第一次出现的右端点位置。
 28};
 29const int N =1E5+7;
 30state st[N*2];
 31int sz, last,rt;
 32char s[N];
 33int cnt[2*N],rk[2*N];//for radix sort
 34void sa_init()
 35{
 36    sz = 0;
 37    last = rt = ++sz;
 38    st[1].len = 0;
 39    st[1].link=-1;
 40    ms(st[1].nxt,-1);
 41}
 42void sa_extend(int c,int head)
 43{
 44    int cur = ++sz;
 45    st[cur].len = st[last].len + 1;
 46    st[cur].leftmost = head;
 47    memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
 48    int p;
 49    for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
 50        st[p].nxt[c] = cur;
 51    if (p == -1) {
 52        st[cur].link = rt;
 53    } else {
 54        int q = st[p].nxt[c];
 55        if (st[p].len + 1 == st[q].len) {
 56            st[cur].link = q;
 57        } else {
 58            int clone = ++sz ;
 59            st[clone].len = st[p].len + 1;
 60            st[clone].link = st[q].link;
 61            memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
 62            st[clone].leftmost = st[q].leftmost;
 63            for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
 64                st[p].nxt[c] = clone;
 65            st[q].link = st[cur].link = clone;
 66        }
 67    }
 68    last = cur;
 69}
 70void topo()
 71{
 72    ms(cnt,0); 
 73    for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
 74    for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
 75    for (int i = 1 ; i <= sz  ;i++) rk[cnt[st[i].len]--] = i;
 76}
 77string S;
 78void solve (string S)
 79{
 80    sa_init();
 81    int n = S.length();
 82    int i = 0 ;
 83    while (i<n)
 84    {
 85    int now = rt;
 86    int len = 0 ;
 87    while (i<n &&st[now].nxt[S[i]-'a']!=-1)
 88    {
 89        now = st[now].nxt[S[i]-'a'];
 90        len++;
 91        sa_extend(S[i]-'a',i);
 92        i++;
 93    }
 94    if (!len)
 95    {
 96        sa_extend(S[i]-'a',i);
 97        printf("%d %d\n",-1,S[i]);
 98        i++;
 99    }
100    else printf("%d %d\n",len,st[now].leftmost-len+1);
101    }
102}
103
104
105int main()
106{
107#ifndef  ONLINE_JUDGE 
108        freopen("./in.txt","r",stdin);
109#endif
110
111    int T;
112    int cas = 0 ;
113    cin>>T;
114    while (T--)
115    {
116        printf("Case #%d:\n",++cas);
117        cin>>S;
118        solve(S);
119    }
120
121
122#ifndef ONLINE_JUDGE  
123    fclose(stdin);
124#endif
125    return 0;
126}