Tomy's fond of a game called 'Fans and Gems' (also known as Gravnic). In the game, he can use fans to collect gems, but he's satisfied with his play only if all the gems are collected with minimal number of steps. The game is played as following:
There are three kinds of gems, one colored red, one colored green and one colored blue. There are walls in the space, as you see. There are also virtual fans everywhere in the game, but you cannot see them. What you can do each time is to select a DIRECTION to which the fans should blow. There are only four directions possible: UP, DOWN, LEFT and RIGHT. Then, the fans will work, pushing all the gems to fly to the selected direction at the same speed, until they cannot move further(blocked by the wall, other gems or a flyer). Then, if there are some gems touching some same-colored gem(touching means adjacent in one of the four directions), they disappear simultaneously. Note that the fans are still working, so some gems may go on moving in that direction after some gems disappeared. The fans stop working when all the gems cannot move any more, and none of them should disappear. There may be some flyers that can be moved by the fans, but they can NEVER disappear.
You are to write a program that finds the minimal number of operations to make all the gems disappear.