MAWORK - Men at work


Every morning you have to drive to your workplace. Unfortunately, roads are under constant repair. Fortunately, administration is aware that this may cause trouble and they enforce a strict rule on roadblocks: roads must be blocked only half of the time. However, contractors are free to schedule their working hours, still they must follow regulations:

  • Working periods (when the road is blocked) and rest periods (when the road is open) must alternate and be of fixed length.
  • The beginning of the day (time zero) must coincide with the beginning of a period.

Write a program that, given a description of the road network and of contractors schedules outputs the minimal time needed to drive from home to work.

Input

The first line of the input contains a number T ≤ 10 that indicates the number of test cases to follow. The road network is represented on a N x N grid and the first line of each test case consists in the number N, 2 ≤ N ≤ 25.

Then follows N lines of N characters that represent the road network at time zero. Those lines are made of "." (standing for open road) and "*" (standing for roadblock) and they encode the rows of the grid in increasing order, while columns are also presented in increasing order. Conventionally, your home is at the position first row, first column, while your workplace is at the position last row, last column. Furthermore, you leave home at time t=0, that is, your starting position is first row, first column at time zero.

At a given time t, your car must be on some "open road" cell. It takes one time unit to drive to any of the four adjacent cells heading toward north, south, west or east, and you may also choose to stay on the same cell for one time unit. Of course, those five moves are valid if and only if the target cell exists and is free at time t+1.

Finally comes N lines of N characters that represent the contractors schedules. Those lines match the ones of the grid description and are made of N characters 0,1,...,9 that specify the duration of the working (and rest) period for a given cell. Observe that 0 is a bit special, since it means that the corresponding cell status does not change.

Output

The output consist in a single line for each test case, holding either the requested time, or NO, if driving from home to work is not possible.

Example

Input:

2
10
.*********
........**
*.******.*
*.******.*
*.******.*
*........*
*.******.*
*.******.*
*........*
********..
0000000000
0000000000
0000000000
0000000000
0000000000
0123456780
0000000000
0000000000
0123456780
0000000000
3
...
**.
**.
021
002
000

Output:

34
NO

hide comments
Rishav Goyal: 2020-09-20 01:46:00

Test cases are not testing the time complexity for complex cases. should add hard test case

lord voldemort: 2015-02-28 00:06:18

data set is very weak
update it

HM Mehrab: 2014-10-08 10:15:01

Actually, brianfry713 from UVa made that test case, not me.

LeppyR64: 2014-05-06 15:10:44

Oh boy. HM Mehrab's test case helped a lot. I didn't realize that the roadblocks ('*') could change to open road ('.').

HM Mehrab: 2014-05-01 07:47:51

Dataset is weak. For the following case, correct output should be 19, but my code outputs 20 and still got AC.

4
.***
..*.
...*
.*..
3818
1081
5548
7739

Aswin Akhilesh: 2011-11-04 14:57:57

Phew! Gotcha!

Last edit: 2012-04-13 00:00:29

Added by:Adrian Kuegel
Date:2004-07-16
Time limit:9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Southwestern European Regional Contest, Paris 2003