Professor Oak nurtures many Pokémon in his Pokémon laboratory. He generally has the habit of gifting young pokémon to budding pokémasters. As of now the professor is grooming a very large number of Pikachu , Togepi and Eevee and is ready to give them away . Strange enough, he does not want to give them for free.

Now, assume there are N chilren waiting to get their first pokémon. Oak makes them stand in a line. He decides that no two neighbouring children must get the same pokémon. The neighbours of a child i are i-1 and i+1. The first and last children are not neighbours. Children can any 1 of the 3 pokémon and pay the specified amount. The cost of a particular pokémon is not the same for all the children. They are assigned randomly.

For example, for one child the costs of pikachu, togepi and eevee are ¤1, ¤100, ¤100 respectively. For another child the costs may be ¤100, ¤1, ¤100 in the same order. The children get agitated . They decide to teach Oak a lesson by purchasing pokémon optimally so that Professor Oak gets the minimum possible amount.

So, given the total number of children and the cost of purchase of these 3 pokémon for each child compute the minimum amount that can be earned by Oak under the constraints that each child gets only one pokémon and no two neighbouring children standing in the line have the same pokémon.

Note: ¤ symbol stands for Indian Rupee.

Input

Line 1 contains the number of test cases t.

Line 2 contains the number of children N for this test case. (N <= 50)

Next lines contain the cost of purchase for each child (in the order Pikachu, Togepi and Eevee) respectively.

Output

Minimal total cost.

Example

Input:
1
3
1 100 100
100 1 100
100 100 1

Output:
3

Input:
1
3
1 100 100
100 100 100
1 100 100

Output:
102

Explanation

In the first example, there are 3 children. For the first child the cost of purchasing Pikachu (P) is ¤1, Togepi (T) is ¤100 and Eevee (E) is ¤100. Similarly the next 2 lines are the costs of purchasing P, T and E for the remaining two children.

If the Pokémon are purchased in the order P, T, E (Pikachu to child1, Togepi to child2 and Eevee to child3) the amount earned by Professor Oak is minimised and that minimised amount is ¤3.