Everyone enjoyed BYTECODE11. So the “Maximum Profit” problem is:

Chakra is a young and dynamic entrepreneur, who is developing rapidly as a successful hotelier. He owns the Quickbyte chain of restaurants, 'M' of which are fully functional now. He divides each day into 'M' time slots. For each time slot 'j', in every restaurant 'i', there are Aij waiters and Bij customers. Being a quality conscious person, he wants each waiter to handle at most one customer in a given time slot. Since he is really busy, in a day each restaurant is open only during one of the time slots. Since the hunger and demand for food varies during the day, the price which the customer is willing to pay varies, and is given by Cij for a restaurant 'i' during a time slot 'j'.Given the values of Aij, Bij and Cij, find the maximum profit which Chakra can make in a day.

Let’s add a constraint “Only one restaurant can be opened in a time slot”. Also the number of restaurants and number of time slots will be equal (‘M’).

Input

The first line of input contains an integer 't', denoting the number of test cases.

For each test case, the first line contains an integer 'M'.

Each of the next 'M' lines contains 'M’ integers. The jth integer on the ith line denotes the value of Aij.

Each of the next 'M' lines contains 'M' integers. The jth integer on the ith line denotes the value of Bij.

Each of the next 'M' lines contains 'M' integers. The jth integer on the ith line denotes the value of Cij.

Output

For each test case output one value, denoting the maximum profit which Chakra can make in a day.

Example

Input:
2
2
1 2
3 2
3 2
1 2
4 5
3 1
3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1000 33 10
75 1000 1000
100 50 39

Output:
13
2050

Constraints

t <= 50

1 <= M <= 15

1 <= Aij, Bij <= 5000

0 <= Cij <= 10^9