A digital string is defined as a string of length \(N\) consisting of the digits \(2\), \(4\), \(6\), or \(8\).

You are given an empty string and the digits have to be entered in this string such that no two adjacent digits are the same.
For each position in the string, you are given four integers \(P,Q,R,S\). These integers denote the cost of entering \(2\), \(4\), \(6\), or \(8\) respectively in that position in the string.

Write a program to determine the minimum cost of a digital string.
Note: \(P\), \(Q\), \(R\), and \(S\) denote the cost of entering the digit \(2\), \(4\), \(6\), or \(8\) in the string respectively

Input format

• First line: \(T\) denoting the number of test cases
• For each test case:
  • First line: \(N\)
  • Next \(N\) lines: \(i^{th}\) line of these \(N\) lines contain four integers \(P,Q,R,S\) denoting the cost of entering \(2\), \(4\), \(6\), or \(8\) respectively in the \(i^{th}\) position in the string

Output format

Print the minimum cost of a digital string.

Constraints

\(1 \le T \le 10 \)

\(1 \le N \le 10^5 \)

\( P, Q, R, S \le 1000\)