Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0034 - PEG SOLITAIRE

   The game of peg solitaire, popular at the court of the French king Louis XIV, has the following rules. Given a two-dimensional board with a mesh of holes, each hole can contain one peg (pin). The only legal move of a peg is a vertical or horizontal jump over an adjacent peg into the empty hole next to the jumped peg in line with it, which is then removed. The original goal of the game was to leave a single peg in the predefined position on the board by performing only legal moves. Obviously, such a solution is possible only for certain board forms and starting configurations. To drop this restriction, we slightly redefine the problem: Given the starting configuration of the board, determine the minimum number of pegs that can be achieved by means of legal moves as well as the minimum number of moves required to reach that number of pegs.

Input

   The first line of the input contains one number, 1 N 100 which represents the number of test cases. Each test case is described by the following lines of input that represent the initial state of the solitaire board.

   In this representation ’.’ denotes an empty hole and ’o’ a hole with a peg in it. ’#’ indicates a part of the board without a hole. All boards have the same shape, see sample input (that includes position of holes). In its initial state, the board can contain at most 8 pegs. There is an empty line between two consecutive test cases.

Output

   For each test case your program should output a line with two numbers separated by a single whitespace, with the first one denoting the minimum number of pegs achievable  by  legal  moves starting with the given initial state, and the second one providing the minimum required number of moves.

Examples

stdin

stdout

1

3                                                                    

###...###                                                     

..oo.....                                            

.....oo..

.........

###...###

 

###...###

..oo.o...

...o.oo..

...oo....

###...###

 

###o..###

.o.oo....

o.o......

.o.o.....

###...###

1 3

1 7

1 7


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-18
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.German (GCPC) 2013.F

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.