Tic Tac Toe grid Didi and Dede are two kids who love to play the famous game of tic-tac-toe all the time, but, right now, they have a problem: the final exams from school are coming up. Being quite smart, they came up with a way to play the game and study at the same time! Before learning about Didi and Dede’s new (and improved) version of Tic Tac Toe, let’s remember the rules of the original game: there’s a 3 × 3 board that’s initially empty and players take turns selecting one empty space and filling it (one player fills it with an “O” and the other fills it with an “X”). The first player to fill the main diagonal or the secondary diagonal or either a complete vertical or horizontal line with 3 of his symbols wins the game. If there are no more positions to fill and none of the players made a winning line, it’s a tie. In their improved version, Didi and Dede assigned to each board place a study subject: the first one got physics, the second one got math, the third one got Portuguese and so on. Then they came up with a lot different exercises for each one of the subjects. The game then goes like this: like in the classic version, the board begins empty; in the player’s turn he can pick any empty position and he will be asked a random question about the subject associated with that position - if he answers it correctly, he’ll put his symbol in the position, otherwise the opponent’s symbol will be placed there. The winning condition is the same of the classic version. Even tough they came up with this game to study, Didi and Dede hate to lose! They know that who plays first has a better chance to win, so they always try to win when playing first and try not to loose when playing second. They also know each other very well (after all those years playing tic-tac-toe and studying together), so they know what’s the probability that each one has to answer correctly one question on any subject. Input The first line of input gives the number of cases, T (1 ≤ T ≤ 50). T test cases follow. A test case starts with a blank line. Then you will have two 3 × 3 grids for the first and second player, respectively. Each grid has 9 integers from 0 to 100 (included), being given 3 integers per line. These numbers correspond to the probability of the player gets a correct answer for the related position (study subject). Output The output is comprised of one line for each input data set. For each test case output ‘Case #C:’ (where C is the number of the current test case) followed by the probability of the first player wins, rounded to 2 decimals, if both players had the capacity of playing optimizing their goals. Sample Input 5 000 000 000
2/2 100 100 100 100 100 100 100 100 100 100 0 0 100 0 0 100 0 0 0 100 100 0 100 100 0 100 100 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 0 0 50 0 0 50 0 0 0 100 100 0 100 100 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 Sample Output Case #1: 0.00 Case #2: 100.00 Case #3: 47.46 Case #4: 12.50 Case #5: 0.00