Mike has got a huge array b, and he is told that the array is encrypted.
The array is encrypted as follows.
Let ai(0≤i<n) be the i-th number of this original array.
Let bi(0≤i<n) be the i-th number of this encrypted array.
Let n be a power of 2, which means n=2k.
The bi is calculated as following.
f(x) means, if the number of 1 in the binary of x is even, it will return 1, otherwise 0.
Mike want to inverse the procedure of encryption.
Please help him recover the array a with the array b.
The first line contains an integer T(T≤5), denoting the number of the test cases.
For each test case, the first line contains an integer k(0≤k≤20),
The next line contains n=2k integers, which are bi respectively.
It is guaranteed that, ai is an integer and 0≤ai≤109.
打印一个矩阵，(i,j)为f((i or j)xor i),就会发现矩阵平均分成四块，就是
其中每一个A都可以分成这样四个矩阵。如果f((i or j)xor i)换成f((i or j)xor i)*a[j]，那么第i行的和就是b[i]。根据矩阵特性可以处理成前面一半的b只包含前一半的a，后一半的b只包含后一半的a。也就是四个矩阵中只留下左上角和右下角，其他都变成了0，然后递归分治。