You are given two arrays A and B of length N. Let S be the set of integers from 1 to N. Can you find the maximum possible value of (Ai1+Ai2+...+Aik)2+(Bi1+Bi2+...+Bik)2 where {i1,i2...ik} is a non-empty subset of S?
Input Format
The first line contains a single integer T, denoting the number of test cases.
T testcases follow, each test case given in following format.
N
A1 A2 ... AN
B1 B2 ... BN
Output Format
For each test case, output the maximum possible value in one line.
Constraints
1 <= T <= 10
1 <= N <= 1000
-106 <= Ai, Bi <= 106
Sample Input
1
2
-1 5
4 -5
Sample Output
50
Explanation
All possible non-empty subsets for N = 2 of S = {1,2} are {1}, {2} and {1,2}. The maximum possible values of the above equation now are
- (-1)2 + (4)2 = 17
- (5)2 + (-5)2 = 50
- (-1 + 5)2 + (4 - 5)2 = 17
hence 50.
Timelimits
Timelimits for this challenge can be seen here