Flandre Scarlet is a lovely vampire. However, She owns a very dangerous ability that can destroy all the things in front of her, Not in purpose but carelessly , she uses it sometimes, so she was trapped in the basement for a long period of time and always stay alone.
Now, she hopes to see the outwards world, she decides to escape from the basement, thougt it's not an easy task. In order to prevent her from escape, There are many traps in the basement.
There are many levels in the basement.
Level one is the same as a game that we always call "Flip Game".
Now, let me introduce the rules of this level to you.
It is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is "#" and the other one is "*" and each piece is lying either it's "#" or "*" side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from "#" to "*" and vice versa. The pieces to be flipped are chosen every round according to the following rules:
1.Choose any one of the 16 pieces.
2.Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
consider the following position as an example:
**##
##*#
**##
*#*#
If we choose to flip the 2st piece from the 3rd row (this choice is shown at the picture), then the field will become:
***#
#*#*
***#
*#*#
The goal of the Level one is to flip either all pieces "#" side up or all pieces "*" side up.
Flandre is need your help urgently! You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
