Mr. Bhulla, now a member of the Mafia, is ordered by his capo Captain Cold to buy guns, ammunition and masks for the organization. Captain Cold is used to playing games with his men and so gives Bhulla some rules regarding the purchase. He says:

There are N different factories in the market of illegal guns and ammo. Every factory contains all these three items (guns, ammo and masks) but at different prices. Since the Mafia has equal terms with each of the factories, Bhulla has to buy something from each of them.

However, Bhulla cannot buy the same type of item from two adjacent factories, say if he had already bought guns from the factory 'A' and the factory 'B' is adjacent to it, he cannot buy guns from 'B', because if he does so then the competition between the factories will get bloody and the Trade Boss would make him sleep with the fishes.

At the same time he has to minimize the total expenditure spent on buying all the 3 types items. If he is unable, he would be deep frozen by the intolerant Captain Cold. Now Bhulla is confused. Needing a good programmer, he asks for your help to save his life.

You are provided the costs of all three items in each of the N factories. You need to help him find the minimum amount of money that he needs to spend such that he buys exactly one item from each factory.

Input Format

The first line contains T, the number of test cases. For each test case, the first line contains N, the number of factories. N lines follow, each containing 3 space separated integers, giving the cost of guns, ammo and masks respectively at each factory. Factories that are adjacent as per question will appear adjacent in the input.

Output Format

For each test case, print the minimum possible expenditure under the given conditions.

Constraints

1 ≤ T ≤ 15

1 ≤ N ≤ 10⁶

Cost of each item (guns/ammo/masks) is non-negative and does not exceed 10⁴