Let's say you are standing on the XY-plane at point (0, 0) and you want to reach point (n, n).

You can move only in two directions: 

  * to the right, i. e. horizontally and in the direction that increase your x coordinate, 
  * or up, i. e. vertically and in the direction that increase your y coordinate. 



In other words, your path will have the following structure: 

  * initially, you choose to go to the right or up; 
  * then you go some positive integer distance in the chosen direction (distances can be chosen independently); 
  * after that you change your direction (from right to up, or from up to right) and repeat the process. 



You don't like to change your direction too much, so you will make no more than n - 1 direction changes.

As a result, your path will be a polygonal chain from (0, 0) to (n, n), consisting of at most n line segments where each segment has positive integer length and vertical and horizontal segments alternate.

Not all paths are equal. You have n integers c_1, c_2, ..., c_n where c_i is the cost of the i-th segment.

Using these costs we can define the cost of the path as the sum of lengths of the segments of this path multiplied by their cost, i. e. if the path consists of k segments (k ≤ n), then the cost of the path is equal to ∑_{i=1}^{k}{c_i ⋅ length_i} (segments are numbered from 1 to k in the order they are in the path).

Find the path of the minimum cost and print its cost.

Input

The first line contains the single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains the single integer n (2 ≤ n ≤ 10^5).

The second line of each test case contains n integers c_1, c_2, ..., c_n (1 ≤ c_i ≤ 10^9) — the costs of each segment.

It's guaranteed that the total sum of n doesn't exceed 10^5.

Output

For each test case, print the minimum possible cost of the path from (0, 0) to (n, n) consisting of at most n alternating segments.

Example

Input


3
2
13 88
3
2 3 1
5
4 3 2 1 4


Output


202
13
19

Note

In the first test case, to reach (2, 2) you need to make at least one turn, so your path will consist of exactly 2 segments: one horizontal of length 2 and one vertical of length 2. The cost of the path will be equal to 2 ⋅ c_1 + 2 ⋅ c_2 = 26 + 176 = 202.

In the second test case, one of the optimal paths consists of 3 segments: the first segment of length 1, the second segment of length 3 and the third segment of length 2.

The cost of the path is 1 ⋅ 2 + 3 ⋅ 3 + 2 ⋅ 1 = 13.

In the third test case, one of the optimal paths consists of 4 segments: the first segment of length 1, the second one — 1, the third one — 4, the fourth one — 4. The cost of the path is 1 ⋅ 4 + 1 ⋅ 3 + 4 ⋅ 2 + 4 ⋅ 1 = 19.
import os 
import sys 
from io import BytesIO, IOBase  
import heapq as h 
import bisect 
import math as mt
from types import GeneratorType  
BUFSIZE = 8192
class SortedList: 
    def __init__(self, iterable=[], _load=200):
        """Initialize sorted list instance."""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True
 
    def _fen_build(self):
        """Build a fenwick tree instance."""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False
 
    def _fen_update(self, index, value):
        """Update `fen_tree[index] += value`."""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index+1
 
    def _fen_query(self, end):
        """Return `sum(_fen_tree[:end])`."""
        if self._rebuild:
            self._fen_build()
 
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x
 
    def _fen_findkth(self, k):
        """Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`)."""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return 0, k
        if k >= self._len - _list_lens[-1]:
            return len(_list_lens) - 1, k + _list_lens[-1] - self._len
        if self._rebuild:
            self._fen_build()
 
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return idx + 1, k
 
    def _delete(self, pos, idx):
        """Delete value at the given `(pos, idx)`."""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
 
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
 
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True
 
    def _loc_left(self, value):
        """Return an index pair that corresponds to the first position of `value` in the sorted list."""
        if not self._len:
            return 0, 0
 
        _lists = self._lists
        _mins = self._mins
 
        lo, pos = -1, len(_lists) - 1
        while lo + 1 < pos:
            mi = (lo + pos) >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
 
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
 
        _list = _lists[pos]
        lo, idx = -1, len(_list)
        while lo + 1 < idx:
            mi = (lo + idx) >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
 
        return pos, idx
 
    def _loc_right(self, value):
        """Return an index pair that corresponds to the last position of `value` in the sorted list."""
        if not self._len:
            return 0, 0
 
        _lists = self._lists
        _mins = self._mins
 
        pos, hi = 0, len(_lists)
        while pos + 1 < hi:
            mi = (pos + hi) >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
 
        _list = _lists[pos]
        lo, idx = -1, len(_list)
        while lo + 1 < idx:
            mi = (lo + idx) >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
 
        return pos, idx
 
    def add(self, value):
        """Add `value` to sorted list."""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
 
        self._len += 1
        if _lists:
            pos, idx = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True
 
    def discard(self, value):
        """Remove `value` from sorted list if it is a member."""
        _lists = self._lists
        if _lists:
            pos, idx = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)
 
    def remove(self, value):
        """Remove `value` from sorted list; `value` must be a member."""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))
 
    def pop(self, index=-1):
        """Remove and return value at `index` in sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value
 
    def bisect_left(self, value):
        """Return the first index to insert `value` in the sorted list."""
        pos, idx = self._loc_left(value)
        return self._fen_query(pos) + idx
 
    def bisect_right(self, value):
        """Return the last index to insert `value` in the sorted list."""
        pos, idx = self._loc_right(value)
        return self._fen_query(pos) + idx
 
    def count(self, value):
        """Return number of occurrences of `value` in the sorted list."""
        return self.bisect_right(value) - self.bisect_left(value)
 
    def __len__(self):
        """Return the size of the sorted list."""
        return self._len
 
    def __getitem__(self, index):
        """Lookup value at `index` in sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]
 
    def __delitem__(self, index):
        """Remove value at `index` from sorted list."""
        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)
                 
    def __contains__(self, value):
        """Return true if `value` is an element of the sorted list."""
        _lists = self._lists
        if _lists:
            pos, idx = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False
 
    def __iter__(self):
        """Return an iterator over the sorted list."""
        return (value for _list in self._lists for value in _list)
 
    def __reversed__(self):
        """Return a reverse iterator over the sorted list."""
        return (value for _list in reversed(self._lists) for value in reversed(_list))
 
    def __repr__(self):
        """Return string representation of sorted list."""
        return 'SortedList({0})'.format(list(self))
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
import sys
from math import ceil,log2 
  
INT_MAX = sys.maxsize
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
import collections as col
import math, string
 
def getInts():
    return [int(s) for s in input().split()]
 
def getInt():
    return int(input())
 
def getStrs():
    return [s for s in input().split()]
 
def getStr():
    return input()
 
def listStr():
    return list(input())
def minVal(x, y) : 
    return x if (x < y) else y;  
  
# A utility function to get the  
# middle index from corner indexes.  
def getMid(s, e) : 
    return s + (e - s) // 2;  
  
""" A recursive function to get the  
minimum value in a given range  
of array indexes. The following  
are parameters for this function.  
  
    st --> Pointer to segment tree  
    index --> Index of current node in the  
        segment tree. Initially 0 is  
        passed as root is always at index 0  
    ss & se --> Starting and ending indexes  
                of the segment represented  
                by current node, i.e., st[index]  
    qs & qe --> Starting and ending indexes of query range """
def RMQUtil( st, ss, se, qs, qe, index) : 
  
    # If segment of this node is a part  
    # of given range, then return  
    # the min of the segment  
    if (qs <= ss and qe >= se) : 
        return st[index];  
  
    # If segment of this node  
    # is outside the given range  
    if (se < qs or ss > qe) : 
        return INT_MAX;  
  
    # If a part of this segment  
    # overlaps with the given range  
    mid = getMid(ss, se);  
    return minVal(RMQUtil(st, ss, mid, qs,  
                          qe, 2 * index + 1),  
                  RMQUtil(st, mid + 1, se, 
                          qs, qe, 2 * index + 2));  
  
# Return minimum of elements in range  
# from index qs (query start) to  
# qe (query end). It mainly uses RMQUtil()  
def RMQ( st, n, qs, qe) :  
  
    # Check for erroneous input values  
    if (qs < 0 or qe > n - 1 or qs > qe) : 
      
        print("Invalid Input");  
        return -1;  
      
    return RMQUtil(st, 0, n - 1, qs, qe, 0);  
  
# A recursive function that constructs  
# Segment Tree for array[ss..se].  
# si is index of current node in segment tree st  
def constructSTUtil(arr, ss, se, st, si) : 
  
    # If there is one element in array,  
    # store it in current node of  
    # segment tree and return  
    if (ss == se) : 
  
        st[si] = arr[ss];  
        return arr[ss];  
  
    # If there are more than one elements,  
    # then recur for left and right subtrees  
    # and store the minimum of two values in this node  
    mid = getMid(ss, se);  
    st[si] = minVal(constructSTUtil(arr, ss, mid, 
                                    st, si * 2 + 1), 
                    constructSTUtil(arr, mid + 1, se, 
                                    st, si * 2 + 2));  
      
    return st[si];  
  
"""Function to construct segment tree  
from given array. This function allocates  
memory for segment tree and calls constructSTUtil() 
to fill the allocated memory """
def constructST( arr, n) : 
  
    # Allocate memory for segment tree  
  
    # Height of segment tree  
    x = (int)(ceil(log2(n)));  
  
    # Maximum size of segment tree  
    max_size = 2 * (int)(2**x) - 1;  
   
    st = [0] * (max_size);  
  
    # Fill the allocated memory st  
    constructSTUtil(arr, 0, n - 1, st, 0);  
  
    # Return the constructed segment tree  
    return st;  
  
 
MOD = 10**9+7
mod=10**9+7
#t=1
p=10**9+7
def ncr_util():
    
    inv[0]=inv[1]=1
    fact[0]=fact[1]=1
    for i in range(2,300001):
        inv[i]=(inv[i%p]*(p-p//i))%p
    for i in range(1,300001):
        inv[i]=(inv[i-1]*inv[i])%p
        fact[i]=(fact[i-1]*i)%p

def z_array(s1):
    n = len(s1)
    z=[0]*(n)
    l, r, k = 0, 0, 0
    for i in range(1,n): 
  
        # if i>R nothing matches so we will calculate. 
        # Z[i] using naive way. 
        if i > r: 
            l, r = i, i 
  
            # R-L = 0 in starting, so it will start 
            # checking from 0'th index. For example, 
            # for "ababab" and i = 1, the value of R 
            # remains 0 and Z[i] becomes 0. For string 
            # "aaaaaa" and i = 1, Z[i] and R become 5 
            while r < n and s1[r - l] == s1[r]: 
                r += 1
            z[i] = r - l 
            r -= 1
        else: 
  
            # k = i-L so k corresponds to number which 
            # matches in [L,R] interval. 
            k = i - l 
  
            # if Z[k] is less than remaining interval 
            # then Z[i] will be equal to Z[k]. 
            # For example, str = "ababab", i = 3, R = 5 
            # and L = 2 
            if z[k] < r - i + 1: 
                z[i] = z[k] 
  
            # For example str = "aaaaaa" and i = 2,  
            # R is 5, L is 0 
            else: 
  
                # else start from R and check manually 
                l = i 
                while r < n and s1[r - l] == s1[r]: 
                    r += 1
                z[i] = r - l 
         
                r -= 1  
    return z
'''       
MAXN1=100001
spf=[0]*MAXN1

def sieve():
    prime=[]
    spf[1]=1
    
    for i in range(2,MAXN1):
        spf[i]=i
    for i in range(4,MAXN1,2):
        spf[i]=2
    for i in range(3,math.ceil(math.sqrt(MAXN1))):
        if spf[i]==i:
            for j in range(i*i,MAXN1,i):
                if spf[j]==j:
                    spf[j]=i
    for i in range(2,MAXN1):
        if spf[i]==i:
            prime.append(i)
    return prime

prime=sieve()
 
def factor(x):
    d1={}
    x1=x
    while x!=1:
        d1[spf[x]]=d1.get(spf[x],0)+1
        x//=spf[x]
    return d1 

def primeFactors(n): 
    d1={}  
    while n % 2 == 0: 
        d1[2]=d1.get(2,0)+1 
        n = n / 2
          
    for i in range(3,int(math.sqrt(n))+1,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            d1[i]=d1.get(i,0)+1 
            n = n // i 
              
    
    if n > 2: 
        d1[n]=d1.get(n,0)+1
    return d1
'''
def fs(x):
    if x<2:
        return 0
        
    return (x*(x-1))//2
t=int(input())
#t=1


def solve():
    min1=l[0]
    min2=l[1]
    cnt=0
    ans=(n*min1+n*min2)
    ans1=min1+min2
    for i in range(2,n):
        ans1+=l[i]
        if cnt%2==0:
            min1=min(l[i],min1)
            ans=min(ans,ans1+(n-(i+2)//2)*min1+(n-(i+1)//2)*min2)
        else:
            min2=min(l[i],min2)
            ans=min(ans,ans1+(n-(i+2)//2)*min2+(n-(i+1)//2)*min1)
        cnt+=1
    return ans
            
        
    
        
    
for _ in range(t):
    #d={}
    n=int(input())
    # n,m=map(int,input().split())
    # l=[]
    # for __ in range(n):
    #     l.append(list(map(int,input().split())))
    #n=int(input())
    #b=input()
    #s=input()
    l=list(map(int,input().split()))
    # a=list(map(int,input().split()))
    # b=list(map(int,input().split()))
    #l.sort()
    #l2=list(map(int,input().split()))
    #l.sort()
    #l.sort(revrese=True)
    #x,y=(map(int,input().split()))
    #l=str(n)
    #l.sort(reverse=True)
    #l2.sort(reverse=True)
    #l1.sort(reverse=True)
    #(solve())
    print(solve()) 
    #print(n,u,r,d,l)
        