You are playing a marble game. You place some marbles in some of the cells of a square board such that each occupied cell contains only 1 marble.

A cell x is considered a dominated cell if it meets either of the following criteria:

• It contains a marble
• All the 4 cells that are adjacent to the cell x contain a marble

Two cells are considered adjacent if they have a common side. Each cell can have four adjacent cells. The cells in the corners and along the sides will have fewer adjacent cells.

Each cell has a separate value for the following parameters:

• Cost of placing a marble into that cell
• Benefit received when the cell is dominated

At the end of the game, the number of points that you score is equal to the difference between the total cost of placing the marbles into the cells and the total benefits that you receive from the dominated cells.

Write a program to calculate the total points that you score based on the following information:

• Cost of placing a marble in each cell
• Benefits that you received by dominating each cell
• Required final state of the board.

Input format

• First line: T (Number of test cases)
  
• First line in each test case: N (Number of cells in each row)
• Next N lines in each test case: N space-separated integers (denoting the cost of placing a marble in each cell)
• Next N lines in each test case: N space-separated integers (denoting the benefit that is received if the cell is dominated)
• Next N lines in each test case: A string of N characters, either ‘*’ or ‘.’ ( ‘*’ represents a cell that contains a marble while ‘.’ represents an empty cell)

Output format

For each test case, print the total number of points scored in the game.

Constraints

$0 ≤ T ≤ 100$
$2 ≤ N ≤ 20$
$0 ≤ cost[i][j], benefit[i][j] ≤ 9$
$0 ≤ i,j ≤ N$