//#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define foru(i,a,b) for(i=(a);i<=(b);i++)
#define ford(i,a,b) for(i=(a);i>=(b);i--)
const int maxn=110000;
char s[maxn],ans_s[maxn],a[maxn],b[maxn];
int n;
int start[maxn],next[maxn] , extended_l[maxn] , extended_r[maxn];
int ans;
void prepare_extended_kmp(char s[],char t[],int extended[],int s1,int t1,int limit){
int i,j,a,len,l;
char k1;
k1=s[limit+1]; s[limit+1]='#';
len=0;
while (t[t1+len]==t[t1+1+len]) len++;
next[t1+1]=len;
a=t1+1;
foru(i,t1+2,limit){
len=a+next[a] - i;
l=next[i-a+1 +t1-1];
if (l<len) next[i]=l;
else {
j=max(0,len);
while (t[t1+j] == t[i+j]) j++;
next[i]=j;
a=i;
}
}
if (s1!=t1){
len=0;
while (s[s1+len]==t[t1+len]) len++;
extended[s1]=len;
a=s1;
}
foru(i,s1+1,t1-1){
len=a+extended[a] - i;
l=next[i-a+1 +t1-1];
if (l<len) extended[i]=l;
else{
j=max(0,len);
while (t[t1+j] == s[i+j]) j++;
extended[i]=j;
a=i;
}
}
foru(i,t1+1,limit) extended[i]=next[i];
s[limit+1]=k1;
}
bool check(int start,int len){
int m1,i;
m1=strlen(ans_s);
i=0;
while (i<m1 && i<len) {
if (a[start+i]!=ans_s[i]) return a[start+i]<ans_s[i];
i++;
}
if (len<m1) return true; else return false;
}
void push_s(int start,int len){
int i;
rep(i,len) ans_s[i]=a[start+i];
ans_s[len]=0;
}
int make_small(int s ,int t, int len , int num){
int i,j,k,u,n;
n=t-s+1;
j=s;
bool flag;
foru(i,1,n-len) {
k=s+i;
flag=false;
rep(u,num) if (a[j+u]!=a[k+u])
if (a[j+u]>a[k+u]) { flag=true; break;}
else { flag=false; break;}
if (flag) j=k;
}
return j;
}
void make_ans(int left,int right){
int i,j,k,mid;
if (left>=right) return;
mid=(left+right)/2;
prepare_extended_kmp(a , a , extended_r , left , mid , right);
prepare_extended_kmp(b , b , extended_l , start[right] , start[mid] , start[left]);
//{====left=======}
int len,st;
foru(i,left,mid-1)
if (i+extended_r[i]-1>=mid-1) {
len=extended_r[i]+extended_l[start[i]] + (mid-i) - 1;
//len=extended_r[i] + (mid-i) ;
k=len / (mid-i);
len=k*(mid-i);
st=make_small(i-extended_l[start[i]]+1,mid+extended_r[i]-1,len,k);
if (k>ans) {
ans=k;
push_s(st, len);
// printf("%s\n",ans_s);
}
else
if (k==ans)
if (check(st,len))
push_s(st,len);
// printf("%s\n",ans_s);
}
// {====right=======}
ford(i,right,mid+1)
if (i-extended_l[start[i]]+1<=mid+1){
len=extended_r[i]+extended_l[start[i]] + (i-mid) - 1;
//len=extended_l[start[i]] + (i-mid) ;
k=len / (i-mid);
len=k*(i-mid);
st=make_small(mid-extended_l[start[i]]+1,i+extended_r[i]-1,len,k);
if (k>ans) {
ans=k;
push_s(st, len);
// printf("%s\n",ans_s);
}
else
if (k==ans)
if (check(st,len))
push_s(st,len);
}
make_ans(left,mid-1);
make_ans(mid+1,right);
}
void work(){
int i,j,k;
foru(i,1,n) {
a[i]=s[i];
b[i]=s[n-i+1];
start[n-i+1]=i;
}
ans=1;
rep(i,n) ans_s[i]=a[i+1];
ans_s[n]=0;
//printf("%s\n",ans_s);
make_ans(1,n);
// printf("%d\n",ans);
printf("%s\n",ans_s);
}
int main(){
int i,j,k,test=0;
while (1){
scanf("%s",s);
if (s[0]=='#') break;
test++;
printf("Case %d: ",test);
n=strlen(s);
ford(i,n,1) s[i]=s[i-1];
work();
}
return 0;
}
