Problem B: The Most Potent Corner 

Problem

Every corner of the N-dimensional (1 < N < 15) unit cube has weight
(some positive integer less than 256). We will call two corners
neighbouring, if they have common edge. Potency of the corner is the
sum of weights of all neighbouring corners. Weights of all the corners
are given. You are to determine two neighbouring corners that have the
maximum sum of potencies and to output this sum.

Input

The first line will give the number of problem instances.  The rest
of the input will consist of one input block for each instance. 
Each input block begins with the integer N, the dimension of the cube. 
Then there are weights of the corners, one per line in the natural 
order: the first line contains the weight of the corner (0,...0,0,0), 
the second one - the weight of (0,...,0,0,1), then there is the weight of
(0,...,0,1,0), then (0,...,0,1,1), then (0,...,1,0,0), the penultimate
line contains the weight of the corner (1,...,1,1,0), the last one -
(1,...,1,1,1).

Output

For each input block the output line should contain one number, the
maximum potencies sum.

Sample Input
------------
2
3
82
73
8
49
120
44
242
58
2
1
1
1
1


Sample Output
-------------
619
4



_______________________________________________________________________________
Modified from acm.uva.es/p/v102/10264.html

 Sergey Karpovich, 2002