Pasha 有一个大小为 $n \times m$ 的棋盘。一些格子被涂成黑色，一些被涂成绿色，其余的格子被涂成白色。此外，Pasha 有一套标准的 28 张多米诺骨牌。他想按照以下方式在棋盘上放置一些骨牌：

• 每张骨牌恰好占据两个相邻的格子；
• 每个非黑色格子恰好被一张骨牌占据；
• 没有任何黑色格子被骨牌占据；
• 绿色格子上的点数总和 $g$ 最大化。

你需要编写一个程序，求出给定棋盘下 $g$ 的最大可能值。

输入格式

输入包含多组测试数据。每组测试数据的第一行包含两个正整数 $n$ 和 $m$ ($1 \le n \cdot m \le 56$)。接下来的 $n$ 行，每行包含 $m$ 个字符。第 $i$ 行描述了棋盘的第 $i$ 行：‘W’ 表示白色格子，‘B’ 表示黑色格子，‘G’ 表示绿色格子。每个棋盘至少包含一个绿色格子。最后一行包含两个零，表示输入结束，不需要处理。输入中最多有 500 组测试数据。

输出格式

对于每组测试数据，输出其编号以及 $g$ 的最大值。如果无法按上述方式放置骨牌，则输出 “No solution”。请遵循样例输出的格式。

样例

输入格式 1

4 4
GWWW
GWWB
BWWB
BWWG
1 3
WGW
0 0

输出格式 1

Case 1: 18
Case 2: No solution

说明

下图展示了如何在第一个样例中放置骨牌：

下图展示了如何在第一个样例中放置骨牌：