Power Swapper

In a parallel universe people are fond of powers of two, and they sort permutations of the numbers $1$ to $2^N$ with one restricted operation. Positions are numbered from $0$.

A range of positions is valid for size $k$ when it consists of $2^k$ adjacent positions and its first position is a multiple of $2^k$. A swap of size $k$ exchanges the contents of two distinct valid ranges of size $2^k$. Swapping a range with itself is not allowed.

To sort a permutation you may use at most one swap of each size $k$, for $k = 0, 1, \dots, N-1$.

For instance [3, 6, 1, 2, 7, 8, 5, 4], a permutation of $1$ to $2^3$, is sorted like this.

• [3, 6, 1, 2, 7, 8, 5, 4]: a swap of size $2$ exchanges [3, 6, 1, 2] and [7, 8, 5, 4].
• [7, 8, 5, 4, 3, 6, 1, 2]: a swap of size $0$ exchanges [5] and [3].
• [7, 8, 3, 4, 5, 6, 1, 2]: a swap of size $1$ exchanges [7, 8] and [1, 2].
• [1, 2, 3, 4, 5, 6, 7, 8]: the array is sorted.

Each of the sizes $0$, $1$ and $2$ was used at most once, and every range started at a position that is a multiple of its own size.

Count the ways to sort the given permutation under these rules. A way is an ordered sequence of swaps, and two ways are the same only when the sequences are identical.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains one integer $N$. The second line contains $2^N$ space separated integers that form a permutation of $1, 2, \dots, 2^N$.

• $1 \le T \le 200$
• $1 \le N \le 12$

For each test case print one line of the form Case #x: y, where x is the test case number starting from $1$ and y is the number of ways to sort the given permutation.