Now-a-days, Manish is becoming  famous for bank robbery in the country because of his cleverness, he never robs own his own.He has four workers A , B, C, and D , all working under him.All of the four take some amount for that. There are total N banks in the country and Manish wants to rob all the banks with minimum

amount spent on workers.Only one worker is allowed to rob the ith bank but following a condition that if one worker robs ith bank, then he can't rob (i+1) th bank.

So ,Manish wants you to calculate minimum amount that he has to spend on all workers to rob all N banks.

-----Input Format-----
First line consists number of test cases T.For each test case,

first line consists an integer N, number of banks in the country

and the next N line consists 4 integers amount taken by A,B,C and D respectively to rob ith bank.

-----Output format-----
For each test case ,output an integer, minimum amount paid  by Manish in separate line .

-----Constraint-----
- 1<=T<=1000
- 1<=N<=100000
- 1<=amount<=100000

-----Subtasks-----
Subtask-1 (10 points)
- 1<=T<=5
- 1<=N<=10
- 1<=amount<=10
Subtask-1 (30 points)
- 1<=T<=100
- 1<=N<=1000
- 1<=amount<=1000
Subtask-1 (60 points)
Original Constraints 
Sample Input
1
3
4 7 2 9
5 6 4 7
2 6 4 3

Sample Output
10

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
for t in range(int(input())):
	n = int(input())
	l = []
	m = []
	x = list(map(int, input().split()))
	l.append(x)
	m.append(list(x))
	for i in range(1, n):
		x = list(map(int, input().split()))
		l.append(x)
		temp = []
		for i in range(4):
			temp.append(x[i] + min(m[-1][:i] + m[-1][i + 1:]))
		m.append(temp)
	print(min(m[-1]))


for t in range(eval(input())):
	dp = [[0 for i in range(4)] for j in range(2)]
	ret = 1
	for u in range(eval(input())):
		c = list(map(int, input().split()))
		for i in range(4):
			dp[u & 1][i] = 1e+18
			for j in range(4):
				if j != i:
					dp[u & 1][i] = min(dp[u & 1][i], c[j] + dp[1 - (u & 1)][j])
					ret = min(dp[u & 1])
	print(ret)