1. 

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11 
 * Problem: 10192 - Vacation 
 * Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1133&mosmsg=Submission+received+with+ID+8431359
 * 
 * @author Manuel Hager
 * @version 1.0, 12/01/2010
 * 
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime: 0.008
 */

#include <iostream>
#include <string>

using namespace std;

#define CITIES 101

char line1[CITIES];
char line2[CITIES];
int strLen1 = 0;
int strLen2 = 0;
int i, j;
int testcase = 1;

int LCS() {
	strLen1 = strlen(line1);
	strLen2 = strlen(line2);
	
	int c[strLen1+1][strLen2+1];
	
	for(i = 0; i <= strLen1; i++) {
		c[i][0] = 0;
	}
	for(j = 0; j <= strLen2; j++) {
		c[0][j] = 0;
	}
	
	for(i = 1; i <= strLen1; i++) {
		for(j = 1; j <= strLen2; j++) {
			if(line1[i - 1] == line2[j - 1]) {
				c[i][j] = c[i -1][j -1] + 1;
			}
			else {
				c[i][j] = max(c[i][j -1], c[i -1][j]);
			}
		}
	}
	
	return c[strLen1][strLen2];
}

int main(int argc, char* argv[])
{
	cin.getline (line1,CITIES);
	while(line1[0] != '#') {
		cin.getline(line2, CITIES);
		printf("Case #%d: you can visit at most %d cities.\n", testcase++, LCS());
		cin.getline(line1, CITIES);
	}
	return 0;
}