{"raw_statement":[{"iden":"statement","content":"Do you like puzzles, fruits and the notion of crossing a snake with a bird for no good reason? If the answer to at least one of those questions is yes, then Snakebird might be the game for you. Solve your way through this head-scratcher of a puzzle game and help the snakebirds sate their hunger.\n\nThe game starts with a board of M × N cells, at the beginning each cell is one of the following types.\n\nOn each move, you can select one of the snakebirds, and move it's head to one of the adjacent cells(four directions) to enter an empty/fruit cell. After each move, something magic is happening, your snakebirds are subject to gravity, which means all snakebirds without support start falling until they land on some obstacles(or other snakebirds with support) or dead. Falling on spike or falling out of the board causes dead. The shape of the snakebird doesn't change during the falling.\n\nIt's guaranteed that nothing is going to fall at the beginning.\n\nTo help Redbird, Greenbird and Bluebird win the game, you need to send all snakebirds to heaven alive. Find out the minimal number of moves needed.\n\nThe first line of the input gives the number of test cases, T. T test cases follow.\n\nThe first line of each test case contains 2 numbers M, N, the rows and columns of the board. The following M lines, each line contains N characters representing the board.\n\nFor each test case, output one line containing \"_Case #x: y_\" in the one line. _x_ is the test case number (starting from 1) and _y_ is the minimum moves needed to send all snakebirds to heaven. If it's impossible to do that, output -1 instead.\n\nIn the first test case, the green snakebird can go to left and enter the exit.\n\nIn the second test case, as the gap is too big, it's impossible to enter the exit.\n\nIn the third test case, the red snakebird needs to go right to eat the fruit, then enter the exit.\n\nIn the forth test case, there is a spike in the middle, the snakebird of length 3 is not able to cross through.\n\nIn the fifth test case, the snakebird of length 4 is able to cross through.\n\nIn the sixth test case, the snakebird can just go right twice and jump to the exit.\n\nIn the seventh test case, the snakebird can also jump to the exit, but a spike kills it at the same time it reaches the exit.\n\nThe last sample looks like the picture below.\n\n"},{"iden":"input","content":"The first line of the input gives the number of test cases, T. T test cases follow.The first line of each test case contains 2 numbers M, N, the rows and columns of the board. The following M lines, each line contains N characters representing the board.  1 ≤ T ≤ 10.  1 ≤ N, M ≤ 20.  The total number of fruits, snakebirds head/body on a board is at most 10.  It's guaranteed that nothing is falling at the beginning. "},{"iden":"output","content":"For each test case, output one line containing \"_Case #x: y_\" in the one line. _x_ is the test case number (starting from 1) and _y_ is the minimum moves needed to send all snakebirds to heaven. If it's impossible to do that, output -1 instead."},{"iden":"note","content":"In the first test case, the green snakebird can go to left and enter the exit.In the second test case, as the gap is too big, it's impossible to enter the exit.In the third test case, the red snakebird needs to go right to eat the fruit, then enter the exit.In the forth test case, there is a spike in the middle, the snakebird of length 3 is not able to cross through.In the fifth test case, the snakebird of length 4 is able to cross through.In the sixth test case, the snakebird can just go right twice and jump to the exit.In the seventh test case, the snakebird can also jump to the exit, but a spike kills it at the same time it reaches the exit.The last sample looks like the picture below.  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of safe houses.  \n- Let $ x_k, y_k \\in \\mathbb{Z} $ be the maximum allowed distance and minimum required coins, respectively.  \n- Let $ D_k = (d_{k,1}, d_{k,2}, \\dots, d_{k,n_k}) $ be the sequence of distances, where $ d_{k,i} \\in \\mathbb{Z} $.  \n- Let $ M_k = (m_{k,1}, m_{k,2}, \\dots, m_{k,n_k}) $ be the sequence of coin counts, where $ m_{k,i} \\in \\mathbb{Z} $.  \n- Each safe house $ i \\in \\{1, \\dots, n_k\\} $ is represented by the pair $ (d_{k,i}, m_{k,i}) $, indexed from 1.\n\n**Constraints**  \n1. $ 1 \\le T \\le 500 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_k \\le 500 $  \n   - $ 1 \\le x_k, y_k \\le 1000 $  \n   - $ 1 \\le d_{k,i}, m_{k,i} \\le 1000 $ for all $ i \\in \\{1, \\dots, n_k\\} $\n\n**Objective**  \nFor each test case $ k $, find the smallest index $ i \\in \\{1, \\dots, n_k\\} $ such that:  \n- $ d_{k,i} \\le x_k $  \n- $ m_{k,i} \\ge y_k $  \nand among all such $ i $, it minimizes $ d_{k,i} $, then maximizes $ m_{k,i} $, then minimizes $ i $.  \n\nIf no such $ i $ exists, output $ -1 $.","simple_statement":"Find the best safe house for Haibara:  \nGiven n safe houses, each at distance d_i with m_i coins.  \nChoose the one where:  \n- d_i ≤ x and m_i ≥ y  \n- Among valid ones, pick the closest (smallest d_i)  \n- If tied in distance, pick the one with most coins (largest m_i)  \n- If still tied, pick the smallest index  \n\nIf no house meets the criteria, output -1.","has_page_source":false}