2015
05-23

# A Famous Airport Manager

Mr. B is an airport manager. One day after lunch he looked out of his office and found that the color of each plane in the airport is either blue or green. Before supper he looked the airport again, and found that no plane is in the airport now. He couldn’t remember the order in which the planes took off, but he knew between his two observations no plane had arrived at the airport. In addition, while one plane is setting its way to the takeoff area, the remaining planes must stay at their own position and not move. In other words, considering the planes taking off in a specific order, the first plane will move while others stay at their own position. After the first plane took off, the second plane could move to the takeoff area and so on, until all the planes gone. Now he wants you to find out the number of different possible color sequences he might see, if he watched at the takeoff area during the whole afternoon.

The airport can be divided into 9 square areas (3 rows x 3 columns), and at most one plane can be parked in one area. The area located at the first column of the first row is the "takeoff area". The plane can take off only in the takeoff area. Besides, each plane (including the one in the takeoff area) can move to a vacant neighboring area. Two areas are neighboring if and only if they share an edge.

Each test case contains 3 lines, each of which contains 3 characters ‘*’, ‘B’, ‘G’, denoting that the corresponding area is currently vacant, occupied by a blue plane, or occupied by a green plane, respectively. The first character of the first row is always a ‘*’. There is at least one place in the apron.

There are about 30,000 test cases. Be careful!

Each test case contains 3 lines, each of which contains 3 characters ‘*’, ‘B’, ‘G’, denoting that the corresponding area is currently vacant, occupied by a blue plane, or occupied by a green plane, respectively. The first character of the first row is always a ‘*’. There is at least one place in the apron.

There are about 30,000 test cases. Be careful!

*BB
BBB
BBB
*GB
BBB
BBB

Case 1: 1
Case 2: 8

/************************************************\LINK: http://acm.hdu.edu.cn/showproblem.php?pid=4246CATEGORY: Fudan Local Programming Contest 2012 AUTHOR: zk.huang@qq.comTAG:   LEVEL:	B+MEMO:	v3使用打表 \************************************************/#include<stdio.h>#include<string.h>#define NN 9#define L 6561int ans[L]={1,1,1,1,1,2,1,2,1,1,1,2,1,1,3,2,3,3,1,2,1,2,3,3,1,3,1,1,1,2,1,1,2,2,3,3,1,1,3,1,1,3,3,4,6,2,3,3,3,4,5,3,6,4,1,2,1,2,3,3,1,2,1,2,3,3,3,4,6,3,5,4,1,3,1,3,6,4,1,3,1,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,3,6,2,3,3,3,4,6,3,6,4,1,1,3,1,1,3,3,4,6,1,1,3,1,1,4,3,4,6,3,4,6,4,5,9,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,8,10,3,6,4,6,10,10,4,9,5,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,3,6,4,1,3,1,3,6,3,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,6,10,10,3,6,4,6,10,8,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,3,1,3,6,4,1,4,1,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,4,6,2,3,3,2,3,5,3,6,4,1,1,3,1,1,3,3,4,6,1,1,4,1,1,4,4,5,10,3,4,6,3,4,6,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,9,10,3,6,4,5,9,9,4,9,5,1,1,3,1,1,4,3,3,6,1,1,4,1,1,5,4,4,10,3,3,6,3,4,9,6,6,10,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,4,5,9,6,10,10,3,4,6,4,5,10,6,8,10,4,5,10,5,6,15,10,13,20,6,9,10,9,14,19,10,15,15,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,5,9,8,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,9,14,14,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,8,15,13,5,14,6,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,2,5,3,1,3,1,3,6,4,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,5,9,9,3,6,4,6,10,9,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,3,6,4,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,5,8,9,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,8,13,15,6,10,10,10,15,19,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,9,14,14,4,10,5,10,20,15,5,14,6,1,3,1,3,6,3,1,4,1,3,6,3,6,10,6,3,9,4,1,4,1,4,10,4,1,5,1,3,6,4,6,10,8,4,10,5,6,10,9,10,15,15,9,19,14,4,10,5,10,20,13,5,15,6,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,5,1,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,4,6,2,3,3,3,4,6,3,6,4,1,1,3,1,1,3,3,4,6,1,1,4,1,1,4,4,5,10,3,4,6,4,5,9,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,9,5,1,1,3,1,1,3,3,4,6,1,1,3,1,1,4,3,4,6,3,4,6,4,5,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,4,1,1,4,4,5,10,4,5,10,5,6,13,10,15,20,3,3,6,3,4,6,6,8,10,3,4,6,4,5,10,6,9,10,6,9,10,9,14,16,10,17,15,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,9,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,13,10,15,20,6,10,10,10,15,17,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,18,15,4,9,5,9,16,14,5,13,6,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,3,4,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,5,1,1,5,5,6,15,4,5,10,4,5,10,10,15,20,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,10,10,9,14,19,10,19,15,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,4,5,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,5,1,1,5,5,6,15,4,5,10,5,6,14,10,15,20,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,10,10,9,14,19,10,19,15,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,10,15,20,6,10,10,9,14,18,10,20,15,4,5,10,5,6,13,10,15,20,5,6,15,6,7,19,15,21,35,10,15,20,14,20,27,20,35,35,6,10,10,10,15,20,10,18,15,10,15,20,15,21,35,20,33,35,10,19,15,18,30,33,15,33,21,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,5,9,9,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,9,14,19,6,10,10,10,15,19,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,9,16,14,4,10,5,10,20,15,5,14,6,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,8,13,15,6,10,10,10,15,19,10,20,15,4,5,10,5,6,13,10,15,20,5,6,14,6,7,18,13,19,29,10,15,20,15,21,32,20,35,35,6,9,10,9,14,16,10,17,15,9,14,16,14,20,30,15,25,24,10,19,15,19,34,31,15,31,21,3,6,4,6,10,9,4,10,5,6,10,9,10,15,16,9,19,14,4,10,5,10,20,14,5,15,6,6,10,10,10,15,17,10,20,15,10,15,19,15,21,29,19,34,34,10,20,15,20,35,32,15,35,21,4,9,5,9,16,14,5,13,6,9,16,14,16,25,30,14,28,20,5,14,6,14,30,20,6,19,7,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,3,6,4,1,3,1,3,6,4,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,6,10,10,3,6,4,6,10,9,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,13,9,14,16,6,10,10,10,15,18,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,17,15,4,10,5,10,20,15,5,13,6,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,3,1,3,6,4,1,4,1,3,6,3,6,10,8,3,6,4,6,10,9,10,15,17,9,16,14,3,6,4,6,10,9,4,10,5,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,13,6,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,5,9,9,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,9,14,16,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,10,5,9,19,14,5,14,6,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,9,10,9,14,19,10,16,15,4,5,9,5,6,13,9,14,16,5,6,14,6,7,19,14,20,30,9,14,16,14,20,28,16,30,25,6,10,10,10,15,20,10,17,15,10,15,20,15,21,35,20,32,35,10,19,15,19,34,34,15,29,21,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,8,15,13,5,14,6,6,10,9,10,15,17,9,16,14,10,15,19,15,21,31,19,31,34,9,16,14,15,24,25,14,30,20,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,15,32,21,5,14,6,13,29,19,6,18,7,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,3,9,4,1,4,1,4,10,5,1,5,1,3,6,4,6,10,9,4,10,5,6,10,10,10,15,19,9,19,14,4,10,5,10,20,14,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,4,10,5,1,5,1,5,15,6,1,5,1,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,9,18,14,4,10,5,10,20,15,5,15,6,6,10,10,10,15,18,10,20,15,10,15,19,15,21,33,18,33,30,10,20,15,20,35,33,15,35,21,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,14,27,20,5,15,6,15,35,21,6,19,7,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,5,1,3,6,4,6,10,9,4,10,5,6,10,10,10,15,19,9,19,14,4,10,5,10,20,14,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,5,1,5,15,6,1,5,1,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,4,6,2,3,3,3,4,6,3,6,4,1,1,3,1,1,3,3,4,6,1,1,4,1,1,4,4,5,10,3,4,6,4,5,9,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,9,5,1,1,3,1,1,3,3,4,6,1,1,3,1,1,4,3,4,6,3,4,6,4,5,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,4,1,1,4,4,5,10,4,5,10,5,6,13,10,15,20,3,3,6,3,4,6,6,8,10,3,4,6,4,5,10,6,9,10,6,9,10,9,14,16,10,17,15,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,9,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,13,10,15,20,6,10,10,10,15,17,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,18,15,4,9,5,9,16,14,5,13,6,1,1,2,1,1,3,2,3,3,1,1,3,1,1,4,3,4,6,2,3,3,3,4,6,3,6,4,1,1,3,1,1,3,3,4,6,1,1,4,1,1,4,4,5,10,3,4,6,4,5,9,6,10,10,2,3,3,3,4,6,3,5,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,9,5,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,4,10,3,4,6,4,5,9,6,10,10,1,1,4,1,1,4,4,5,10,1,1,4,1,1,5,4,5,10,4,5,10,5,6,13,10,15,20,3,4,6,4,5,10,6,8,10,4,5,10,5,6,15,10,13,20,6,9,10,9,14,19,10,18,15,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,9,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,10,15,17,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,9,16,14,5,14,6,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,5,9,9,3,6,4,6,10,10,4,10,5,3,4,6,4,5,8,6,10,10,4,5,10,5,6,13,9,14,19,6,10,10,10,15,18,10,20,15,3,6,4,6,10,10,4,8,5,6,10,10,10,15,20,9,15,14,4,10,5,10,20,15,5,13,6,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,8,12,15,6,10,10,10,15,19,10,20,15,4,5,10,5,6,13,10,15,20,5,6,13,6,7,18,12,18,25,10,15,20,15,21,32,20,35,35,6,9,10,9,14,16,10,17,15,9,14,16,14,20,30,15,23,24,10,19,15,19,34,31,15,31,21,3,6,4,6,10,9,4,10,5,6,10,9,10,15,16,9,19,14,4,10,5,10,20,13,5,15,6,6,10,10,10,15,17,10,20,15,10,15,19,15,21,28,19,34,34,10,20,15,20,35,30,15,35,21,4,9,5,9,16,14,5,13,6,9,16,14,16,25,30,14,27,20,5,13,6,13,26,19,6,18,7,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,4,5,10,6,10,10,1,1,4,1,1,4,4,5,10,1,1,5,1,1,5,5,6,15,4,5,10,5,6,14,10,15,20,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,10,10,10,15,20,10,19,15,1,1,4,1,1,4,4,5,10,1,1,4,1,1,5,4,5,10,4,5,10,5,6,14,10,15,20,1,1,5,1,1,5,5,6,15,1,1,5,1,1,5,5,6,15,5,6,15,6,7,19,15,21,35,4,4,10,4,5,10,10,13,20,4,5,10,5,6,15,10,14,20,10,14,20,14,20,30,20,32,35,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,10,15,20,6,10,10,10,15,19,10,20,15,4,5,10,5,6,14,10,15,20,5,6,15,6,7,19,15,21,35,10,15,20,15,21,31,20,35,35,6,10,10,10,15,20,10,19,15,10,15,20,15,21,35,20,33,35,10,19,15,19,31,34,15,32,21,1,1,3,1,1,4,3,4,6,1,1,4,1,1,5,4,5,10,3,4,6,4,5,10,6,10,10,1,1,4,1,1,4,4,5,10,1,1,5,1,1,5,5,6,15,4,5,10,5,6,14,10,15,20,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,10,10,10,15,20,10,19,15,1,1,4,1,1,4,4,5,10,1,1,4,1,1,5,4,5,10,4,5,10,5,6,14,10,15,20,1,1,5,1,1,5,5,6,15,1,1,5,1,1,5,5,6,15,5,6,15,6,7,19,15,21,35,4,4,10,4,5,10,10,13,20,4,5,10,5,6,15,10,14,20,10,14,20,14,20,30,20,32,35,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,10,15,20,6,10,10,10,15,19,10,20,15,4,5,10,5,6,14,10,15,20,5,6,15,6,7,19,15,21,35,10,15,20,15,21,31,20,35,35,6,10,10,10,15,20,10,19,15,10,15,20,15,21,35,20,33,35,10,19,15,19,31,34,15,33,21,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,9,14,19,6,10,10,10,15,20,10,20,15,4,5,10,5,6,13,10,15,20,5,6,15,6,7,19,14,20,34,10,15,20,15,21,33,20,35,35,6,10,10,10,15,20,10,18,15,10,15,20,15,21,35,19,30,34,10,20,15,20,35,35,15,33,21,4,5,10,5,6,13,10,15,20,5,6,13,6,7,19,12,18,25,10,15,20,15,21,33,20,35,35,5,6,15,6,7,18,15,21,35,6,7,19,7,8,23,18,25,44,15,21,35,21,28,51,35,56,70,10,13,20,13,19,26,20,30,35,13,19,26,19,26,45,25,39,44,20,33,35,33,54,61,35,63,56,6,10,10,10,15,19,10,20,15,10,15,19,15,21,31,19,34,34,10,20,15,20,35,33,15,35,21,10,15,20,15,21,31,20,35,35,15,21,34,21,28,48,34,55,69,20,35,35,35,56,63,35,70,56,10,19,15,19,31,34,15,32,21,19,31,34,31,46,65,34,61,55,15,33,21,33,61,54,21,51,28,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,10,4,10,5,2,3,5,3,4,6,5,9,9,3,4,9,4,5,10,9,14,19,5,9,9,9,14,16,9,19,14,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,10,5,10,20,15,5,14,6,3,3,6,3,4,6,6,9,10,3,4,6,4,5,10,6,10,10,6,9,10,9,14,16,10,19,15,3,4,9,4,5,9,9,14,19,4,5,9,5,6,14,9,14,19,9,14,19,14,20,28,19,34,34,6,6,10,6,10,10,10,15,15,6,10,10,10,15,20,10,19,15,10,16,15,16,30,25,15,29,21,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,9,16,14,5,14,6,5,9,8,9,14,14,8,15,13,9,14,18,14,20,27,18,30,33,8,15,13,15,24,25,13,29,19,4,10,5,10,20,15,5,14,6,10,20,15,20,35,35,15,33,21,5,14,6,14,30,20,6,18,7,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,9,14,16,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,10,5,10,20,15,5,14,6,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,14,20,6,9,10,9,14,19,10,19,15,4,5,9,5,6,13,9,14,19,5,6,14,6,7,19,14,20,30,9,14,19,14,20,28,19,34,34,6,10,10,10,15,20,10,18,15,10,15,20,15,21,35,20,32,35,10,19,15,19,34,34,15,29,21,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,9,16,14,5,14,6,6,10,9,10,15,17,9,16,14,10,15,19,15,21,31,19,31,34,9,16,14,15,24,25,14,30,20,4,10,5,10,20,15,5,14,6,10,20,15,20,35,35,15,33,21,5,14,6,14,30,20,6,18,7,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,9,19,14,4,10,5,10,20,15,5,15,6,5,9,9,9,14,15,9,19,14,9,14,19,14,20,29,18,33,33,9,19,14,19,34,30,14,34,20,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,14,29,20,5,15,6,15,35,21,6,19,7,6,9,10,9,14,16,10,19,15,9,14,16,14,20,30,15,28,24,10,19,15,19,34,31,15,34,21,9,14,19,14,20,27,19,34,34,14,20,28,20,27,47,27,47,49,19,34,34,34,55,61,34,69,55,10,16,15,16,30,25,15,28,21,16,30,25,30,50,55,24,46,35,15,31,21,31,65,46,21,48,28,4,9,5,9,16,14,5,13,6,9,16,14,16,25,30,14,28,20,5,13,6,13,26,19,6,19,7,8,15,12,15,24,23,12,25,18,15,24,28,24,35,46,27,49,47,12,25,18,25,44,39,18,44,25,5,14,6,14,30,20,6,18,7,14,30,20,30,55,50,20,47,27,6,19,7,19,45,26,7,23,8,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,3,6,4,1,3,1,3,6,4,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,6,10,10,3,6,4,6,10,9,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,13,9,14,16,6,10,10,10,15,18,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,17,15,4,10,5,10,20,15,5,13,6,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,3,1,3,6,4,1,4,1,3,6,3,6,10,8,3,6,4,6,10,9,10,15,17,9,16,14,3,6,4,6,10,9,4,10,5,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,13,6,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,5,9,9,4,10,5,3,4,6,4,5,8,6,10,10,4,5,10,5,6,13,10,15,20,6,10,10,9,14,15,10,20,15,3,6,4,6,10,10,4,8,5,6,10,10,10,15,20,10,18,15,4,10,5,9,19,14,5,13,6,3,4,6,4,5,10,6,9,10,4,5,10,5,6,15,10,13,20,6,9,10,9,14,19,10,16,15,4,5,9,5,6,13,9,14,16,5,6,13,6,7,18,13,19,26,9,14,16,14,20,27,16,30,25,6,10,10,10,15,20,10,17,15,10,15,20,15,21,35,20,30,35,10,19,15,19,34,34,15,28,21,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,19,15,4,9,5,8,15,12,5,14,6,6,10,9,10,15,17,9,16,14,10,15,19,15,21,31,19,31,34,9,16,14,15,24,23,14,30,20,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,15,32,21,5,13,6,12,25,18,6,18,7,1,2,1,2,3,3,1,3,1,2,3,3,3,4,6,3,6,4,1,3,1,3,6,4,1,4,1,2,3,3,3,4,5,3,6,4,3,4,6,4,5,9,6,10,10,3,6,4,6,10,9,4,10,5,1,3,1,3,6,4,1,3,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,5,1,4,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,9,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,9,14,16,6,10,10,10,15,19,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,10,17,15,4,10,5,10,20,15,5,14,6,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,9,5,1,4,1,4,10,4,1,5,1,3,6,4,6,10,8,4,10,5,6,10,9,10,15,18,9,19,14,4,10,5,10,20,13,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,13,6,1,4,1,4,10,5,1,5,1,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,10,15,19,10,20,15,2,5,3,5,9,9,3,6,4,5,9,9,9,14,19,9,16,14,3,9,4,9,19,14,4,10,5,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,9,14,16,6,10,10,10,15,19,10,20,15,4,5,10,5,6,14,10,15,20,5,6,14,6,7,18,14,20,30,10,15,20,15,21,33,20,35,35,5,8,9,8,13,15,9,14,14,8,13,15,13,19,29,15,25,24,9,18,14,18,33,30,14,27,20,3,6,3,6,10,9,3,6,4,6,10,9,10,15,19,9,16,14,3,6,4,6,10,10,4,10,5,6,10,6,10,15,15,6,10,10,10,15,16,15,21,29,16,25,30,6,10,10,10,15,19,10,20,15,3,9,4,9,19,14,4,9,5,9,19,14,19,34,34,14,28,20,4,9,5,9,19,14,5,14,6,3,4,6,4,5,10,6,10,10,4,5,10,5,6,15,10,15,20,6,10,10,9,14,19,10,20,15,4,5,10,5,6,13,10,15,20,5,6,15,6,7,19,15,21,35,10,15,20,14,20,29,20,35,35,5,9,9,9,14,19,9,15,14,9,14,19,14,20,34,19,30,34,9,19,14,18,33,33,14,29,20,4,5,9,5,6,13,9,14,16,5,6,13,6,7,19,13,19,26,9,14,16,14,20,28,16,30,25,5,6,14,6,7,18,14,20,30,6,7,19,7,8,23,19,26,45,14,20,30,20,27,47,30,50,55,8,12,15,12,18,25,15,23,24,12,18,25,18,25,44,25,39,44,15,28,24,27,47,49,24,46,35,6,10,9,10,15,19,9,16,14,10,15,19,15,21,34,19,31,34,9,16,14,15,24,28,14,30,20,10,15,16,15,21,28,16,25,30,15,21,31,21,28,48,31,46,65,16,25,30,24,35,46,30,55,50,9,19,14,19,34,34,14,27,20,19,34,34,34,55,69,34,61,55,14,28,20,27,49,47,20,47,27,2,3,3,3,4,6,3,6,4,3,4,6,4,5,10,6,10,10,3,6,4,6,10,10,4,10,5,3,4,6,4,5,9,6,10,10,4,5,10,5,6,14,10,15,20,6,10,10,10,15,19,10,20,15,3,6,4,6,10,10,4,9,5,6,10,10,10,15,20,9,16,14,4,10,5,10,20,15,5,14,6,3,4,6,4,5,9,6,10,10,4,5,9,5,6,14,9,14,16,6,10,10,10,15,19,10,20,15,4,5,10,5,6,14,10,15,20,5,6,14,6,7,18,14,20,30,10,15,20,15,21,33,20,35,35,6,9,10,9,14,16,10,17,15,9,14,16,14,20,30,15,25,24,10,19,15,19,34,31,15,31,21,3,6,4,6,10,9,4,10,5,6,10,9,10,15,19,9,19,14,4,10,5,10,20,14,5,15,6,6,10,10,10,15,18,10,20,15,10,15,19,15,21,29,19,34,34,10,20,15,20,35,32,15,35,21,4,9,5,9,19,14,5,13,6,9,19,14,19,34,34,14,28,20,5,14,6,14,30,20,6,19,7,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,10,5,1,4,1,4,10,5,1,5,1,3,6,4,6,10,9,4,10,5,6,10,10,10,15,19,10,20,15,4,10,5,10,20,14,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,5,1,5,15,6,1,5,1,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,10,19,15,4,10,5,10,20,15,5,15,6,6,10,10,10,15,19,10,20,15,10,15,19,15,21,32,19,34,31,10,20,15,20,35,33,15,35,21,4,10,5,10,20,15,5,14,6,10,20,15,20,35,35,15,31,21,5,15,6,15,35,21,6,19,7,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,4,1,4,10,5,1,5,1,4,10,4,10,20,13,4,10,5,10,20,14,20,35,32,14,30,20,4,10,5,10,20,14,5,15,6,1,5,1,5,15,6,1,5,1,5,15,6,15,35,21,6,19,7,1,5,1,5,15,6,1,5,1,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,10,20,15,4,10,5,9,19,14,5,15,6,6,10,10,10,15,18,10,20,15,10,15,20,15,21,33,20,35,35,10,20,15,19,34,30,15,35,21,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,15,33,21,5,15,6,14,34,20,6,19,7,6,10,10,10,15,20,10,19,15,10,15,20,15,21,35,20,33,35,10,19,15,19,34,34,15,31,21,10,15,19,15,21,32,19,34,31,15,21,33,21,28,51,33,54,61,19,34,31,34,55,61,31,65,46,10,20,15,20,35,35,15,31,21,20,35,35,35,56,70,35,63,56,15,34,21,34,69,55,21,48,28,4,10,5,10,20,15,5,13,6,10,20,15,20,35,35,15,33,21,5,13,6,12,25,18,6,19,7,10,20,13,20,35,30,13,26,19,20,35,33,35,56,63,33,61,54,13,26,19,25,44,39,19,45,26,5,15,6,15,35,21,6,18,7,15,35,21,35,70,56,21,51,28,6,19,7,18,44,25,7,23,8,1,3,1,3,6,4,1,4,1,3,6,4,6,10,10,4,10,5,1,4,1,4,10,5,1,5,1,3,6,4,6,10,9,4,10,5,6,10,10,10,15,19,10,20,15,4,10,5,10,20,14,5,15,6,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,5,1,5,15,6,1,5,1,3,6,4,6,10,10,4,10,5,6,10,10,10,15,20,10,19,15,4,10,5,10,20,15,5,15,6,6,10,10,10,15,19,10,20,15,10,15,19,15,21,33,19,34,31,10,20,15,20,35,33,15,35,21,4,10,5,10,20,15,5,14,6,10,20,15,20,35,35,15,31,21,5,15,6,15,35,21,6,19,7,1,4,1,4,10,5,1,4,1,4,10,5,10,20,15,5,14,6,1,4,1,4,10,5,1,5,1,4,10,4,10,20,13,4,10,5,10,20,14,20,35,32,14,30,20,4,10,5,10,20,14,5,15,6,1,5,1,5,15,6,1,5,1,5,15,6,15,35,21,6,19,7,1,5,1,5,15,6,1,5,1};int main(){	char str[10];char ch;int k,layout;int ic=1;	while (~scanf("%3s",str)){		scanf("%3s%3s",str+3,str+6);		layout=0;		for (k=1;k<NN;k++){			layout*=3;			if (str[k]=='B') layout+=1;			if (str[k]=='G') layout+=2;		}		printf("Case %d: %d\n",ic++,ans[layout]);	}	return 0;}

/************************************************\LINK: http://acm.hdu.edu.cn/showproblem.php?pid=4246CATEGORY: Fudan Local Programming Contest 2012 AUTHOR: zk.huang@qq.comTAG:   LEVEL:	B+\************************************************/#include<stdio.h>#include<string.h>#include<string>#include<iostream>#include<algorithm>#include<map>#define N 3#define NN N*N#define M 2000#define L 6561using namespace std;struct ST{	bool can[N][N];	//当前点是否可候选（即能否直达0点）};bool chk[N][N];		//当前点是否已遍历		int seq[NN];int nseq;	//temp sequence for DFSint vldseqs[M][NN];int nvldseqs;	//valid sequences calculated by DFSint dirs[][2]={{0,1},{1,0},{0,-1},{-1,0}};int ans[L];void dfs(ST st,int i,int j){	if (i<0||i>=N||j<0||j>=N||chk[i][j]) return;	if (nseq==NN-1){	//save the possible seq		seq[NN-1]=i*N+j;		for (int k=0;k<NN;k++) vldseqs[nvldseqs][k]=seq[k];		nvldseqs++;		return;	}	chk[i][j]=1;		//update chk	int tmp=nseq;	seq[nseq++]=i*N+j;	int k,ii,jj;	for (k=0;k<4;k++){	//update st		ii=i+dirs[k][0];		jj=j+dirs[k][1];		if (ii>=0&&ii<N&&jj>=0&&jj<N) st.can[ii][jj]=1;	}	for (ii=0;ii<N;ii++)		for (jj=0;jj<N;jj++)			if (st.can[ii][jj]) dfs(st,ii,jj);	chk[i][j]=0;	nseq=tmp;}int main(){		int i,j,k;ST st;	memset(chk,0,sizeof(chk));	memset(st.can,0,sizeof(st.can));	st.can[0][0]=1;	dfs(st,0,0);	//for (i=0;i<nvldseqs;i++) {for (j=0;j<NN;j++) printf("%d ",vldseqs[i][j]);printf("\n");};//test	int layout[NN];int x,lay,iseq,kind;	layout[0]=0;	map<int,bool> kmap;	for (lay=0;lay<L;lay++){		k=NN-1;x=lay;		while (k>0){			layout[k--]=x%3;			x=x/3;		}		kmap.clear();		for (iseq=0;iseq<nvldseqs;iseq++){			kind=0;			for (int k=0;k<NN;k++){				x=layout[vldseqs[iseq][k]];				if (x==1) kind=(kind<<1)+0;				if (x==2) kind=(kind<<1)+1;			}			kmap[kind]=1;		}		ans[lay]=kmap.size();			}	freopen("hdu4246.sub.o","w",stdout);	for (i=0;i<L;i++) printf("%d,",ans[i]);	return 0;}