PATHGAME - Path Game

no tags 

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

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with an integer N (1 ≤ N ≤ 50), denoting the length of each row of the grid. Next two lines describe the 2D grid. Each line contains N characters ‘.’ or ‘#’. It is guaranteed that the grid will contain a left-right-right path.

Output

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

Example

Input:
2
5
#....
...#.
25
....#.##.....#...........
..#......#.......#..#....

Output:
2
13

hide comments
vaibhav2303: 2019-05-13 13:32:45

The question can be solved in linear time, the constraints should have been much bigger.

nadstratosfer: 2017-11-12 08:39:44

Enjoyed figuring it out.

hodobox: 2016-12-26 00:17:28

nice one :)

ayush_maan: 2016-07-14 22:33:01

why TLE!!!
can anyone explain?

hodobox: 2016-07-05 20:17:42

2nd input solution ($ are the new black squares)
....#$##...$$#...........
$$#......#.....$$#$$#$$$$
paste into notepad or w/e to see path more clearly.
The number of $ is 13, and more can not be reached, hence ans = 13

varun bumb: 2016-03-30 08:32:37

How come answer for 2nd input is 13?

Ram: 2016-03-26 07:09:05

Made a silly mistake for N =1, costed 2 WA.


Added by:imranziad
Date:2016-03-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:IAPC Round #1