inverse

Mike has got a huge array $b$, and he is told that the array is encrypted.

The array is encrypted as follows.

Let $a_i(0 \leq i < n)$ be the $i$-th number of this original array.

Let $b_i(0 \leq i < n)$ be the $i$-th number of this encrypted array.

Let $n$ be a power of $2$, which means $n = 2^k$.

The $b_i$ is calculated as following.

$$b_i = \sum_{0 \leq j < n} f((i \texttt{ or } j) \texttt{ xor } i) a_j$$

$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 \le 5$), denoting the number of the test cases.

For each test case, the first line contains an integer $k$($0 \leq k \leq 20$),
The next line contains $n = 2^k$ integers, which are $b_i$ respectively.

It is guaranteed that, $a_i$ is an integer and $0 \leq a_i \leq 10^9$.

For each test case, output ''Case #t:'' to represent this is the t-th case. And then output the array $a$.

2
0
233
2
5 3 4 10

Case #1: 233
Case #2: 1 2 3 4

The 2015 ACM-ICPC China Shanghai Metropolitan Programming Contest