Pythagoras

Time Limit: 4000/4000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

Description

Given a list of integers $a_0,a_1,a_2,\cdots,a_{2^k-1}$. Pythagoras triples over $10^9$ are all solutions of $x^2+y^2=z^2$ where $x,y$ and $z$ are constrained to be positive integers less than or equal to $10^9$. You are to compute the sum of $a_{y~mod~2^k}$ of triples $(x,y,z)$ such that $x<y<z$ and they are relatively prime, i.e., have no common divisor larger than $1$.

Input

The first line is an integer $T~(1\le T\le 3)$ indicating the total number of cases.
For each test case the first line is the integer $k~(1\le k\le 17)$.
The second line contains $2^k$ integers corresponding to $a_0$ to $a_{2^k-1}$, where each $a_i$ satisfies $1\le a_i\le 255$.

Output

For each case output the sum of $a_{y~mod~2^k}$ in a line.

Sample Input

3 2 0 0 0 1 2 1 0 0 0 2 1 1 1 1

Sample Output

39788763 79577506 159154994

Hint

liuyiding

Source

2017 ACM/ICPC Asia Regional Qingdao Online

提交代码