SP26705 PATHGAME - Path Game

Cat Snuke is playing the Path Game. The Path Game is played on a rectangular grid of square cells. The grid has 2 rows and some positive number of columns. Each cell is either black or white. A left-to-right path in the grid is a sequence of white cells such that the first cell in the sequence is in the leftmost column, the last cell in the sequence is in the rightmost column, and each pair of consecutive cells shares a common side. The initial coloring of the grid is such that there is at least one left-to-right path. You are given this initial coloring as a 2D string. For each i and j, grid\[i\]\[j\] is either '#' (representing a black cell) or '.' (representing a white cell). Snuke may color some of the white cells black. After he does so, there must still be at least one left-to-right path left on the board. The goal of the game is to color as many cells black as possible. Compute and return the largest number of cells Snuke can color black. (Note that the cells that are already black do not count.)

Input starts with an integer T ( Each case starts with an integer N (1

For each case, print one line containing the answer to the problem.