大陆漂移

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

大陆漂移说认为﹐地球上所有大陆在中生代以前曾经是统一的巨大陆块﹐称之为泛大陆或联合古陆﹐中生代开始﹐泛大陆分裂并漂移﹐逐渐达到现在的位置。
今天我们考虑这个问题的反面,把分离的大陆重新合并在一起。
为了简化计算,我们假设古大陆围成一个正方形,随着时间的推移正方形分裂为K个不同的长方形的大陆,并离开原来的位置。
假设通过卫星给你提供了现在大陆的位置和形状,你任务是首先判断卫星提供的数据能否通过移动合并成一个正方形,否则就是无效的数据。移动的规则是这样的你可以任意移动一个长方形,移动的方向为南,北,东或西。移动过程中部分形状可以组合在一起移动。如果能后合并成一个正方形,请你计算出合并时各个形状移动的最小步骤。正方形最终的位置可以任何地方。合并时形状不能重叠,正方形中间也不能有洞。

Input

 第一行一个整数T(T≤200)表明测试样例的个数。每个测试样例包含20行,每行20个字符。每个字符可能是一个点(“.”)表明空位置,或者是一个字符“x”(ASCII value 120),x表示某个形状的一部分。测试样例开始时有一个空行。

Output

 对于每一个测试样例,如果不能移动合并成一个正方形则输出 “invalid data”,如果能合并成一个正方形则输出完成任务所需的最少的移动步数。
注意:开始时不同的形状不相连,K最多为5.

Sample Input

2 

.................... 
.................... 
.................... 
.................... 
.................... 
.................... 
..xxxxx............. 
..xxxxx............. 
.................... 
.................... 
..xx..........xxx... 
.................... 
..xxxxx............. 
..xxxxx............. 
.................... 
.................... 
.................... 
.................... 
.................... 
.................... 

.................x.. 
.................... 
.................... 
.................... 
..xx................ 
..xx................ 
..xx................ 
..xx................ 
..xx................ 
..xx................ 
.......xxxxxx....... 
.......xxxxxx....... 
.................... 
.................... 
.................... 
....................
.................... 
.................... 
.................... 
....................

Sample Output

Case 1: 13 
Case 2: invalid data

Hint

 

Source

中国海洋大学第四届朗讯杯初级组