<?php

/********************************
*** FACEBOOK HACKER CUP -2012 ***
***    QUALIFICATION ROUND    ***
***     BillBoard Problem     ***
***     C0DER: WHIZZZKID      ***
***  http://n...content-available-to-author-only...a.in/  ***
********************************/

$ip = fopen('php://stdin', "r");		//input resource can be a file
$op = fopen('php://stdout',"w");		//output resource can be a file
$test_cases = trim(fgets($ip));			//first line
$c = 0;

while($c < $test_cases){
	$cc = $c+1;				//just for outputting correct case #n
	$input = trim(fgets($ip));
	$vals = explode(" ", $input);
	$w = array_shift($vals);
	$h = array_shift($vals);
	$string = trim(implode(" ",$vals));
	$type = (string)$string;		//dealing with numbers in the input string
	$str = str_replace(" ","",$type);
	unset($vals);				//to make sure of garbage vals
	$vals = explode(" ", $type);
	$words = count($vals);			//word count
	$bill_area = $w * $h;
	$chars = strlen($str);
	$max_size = floor(sqrt($bill_area / $chars));
	if($max_size < 1){			//last minute optimization improved performance
		$status = 1;
	}else{
		$rows = floor($h / $max_size);
		$cols = floor($w / $max_size);
	}
	while(($rows * $cols) < $chars){	//optimizing... this was a winner!...
		$max_size--;
		$rows = floor($h / $max_size);
		$cols = floor($w / $max_size);
	}
	while($status !== 1){
		$c_cl = $cols;			//it is basically current_columns
		for($i=0; $i<$words; $i++){
			//if we decremented the max_size to 0 there is no point checking further... last minute addition
			if($max_size < 1){
				$status =1;
				break 2;
			}
			//checking if the i th word cannot be accomodated in a single line 
			if($cols < (strlen($vals[$i]))){
				$max_size = floor($w / (strlen($vals[$i])));
				$rows = floor($h / $max_size);
				$cols = floor($w / $max_size);
				break;
			}
			//accomodating the new word
			if($c_cl == $cols){
				$c_cl = $c_cl - (strlen($vals[$i])); //if it is a new line
			}else{
				$c_cl = $c_cl - (strlen($vals[$i])) -1; //-1 is the space between the new and the old word
			}
			
			//backtracking if we made a wrong accommodation
			if($c_cl < 0){
				$rows--;
				$c_cl = $cols - (strlen($vals[$i]));
			}
			//if we are out of rows
			if($rows < 1){		//had to be placed here after error generated by backtracking in the last row
				$max_size--;
				$rows = floor($h / $max_size);
				$cols = floor($w / $max_size);
				break;
			}
			if($i == ($words-1)){
				$status =1;
				break 2;
			}
		}
	}
	if($status ==1){
		fwrite($op, sprintf("Case #%d: %d\n", $cc, $max_size));
		$status = 0;
	}
	$c++;					//incrementing the while loop
}
?>