Power Swapper (Small)

In a parallel universe people are crazy about powers of two, and they sort permutations of the numbers 1 to $2^N$ with the following swap rule.

• A range of $2^k$ adjacent numbers is valid only when its starting position is a multiple of $2^k$. Positions are counted from 0.
• A swap of size $k$ exchanges two distinct valid ranges whose lengths are both $2^k$.

To sort a permutation you may use a swap of size $k$ at most once for each $k$ with $0 \le k < N$. Swapping a range with itself is not allowed.

For example, the permutation $[3, 6, 1, 2, 7, 8, 5, 4]$ of the numbers 1 to $2^3$ can be sorted like this.

• $[3, 6, 1, 2, 7, 8, 5, 4]$: exchange the ranges $[3, 6, 1, 2]$ and $[7, 8, 5, 4]$ with a swap of size 2.
• $[7, 8, 5, 4, 3, 6, 1, 2]$: exchange $[5]$ and $[3]$ with a swap of size 0.
• $[7, 8, 3, 4, 5, 6, 1, 2]$: exchange $[7, 8]$ and $[1, 2]$ with a swap of size 1.
• $[1, 2, 3, 4, 5, 6, 7, 8]$: sorting is done.

This run used the sizes 0, 1 and 2 at most once each, and every exchanged range started at a position that is a multiple of its own length.

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. When the permutation is already sorted, the empty sequence that performs no swap counts as one way.

The first line contains the number of test cases $T$. $T$ test cases follow. The first line of each test case contains a single integer $N$. The second line contains $2^N$ space separated integers, a permutation of $1, 2, \ldots, 2^N$.

Limits

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

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