In a parallel universe, people are crazy about using numbers that are powers of two, and they have defined an exciting sorting strategy for permutations of the numbers from 1 to 2^{N}. They have defined a swapping operation in the following way:
To sort the given permutation, you are allowed to use at most one swap operation of each size k, for k in [0, N). Also, note that swapping a range with itself is not allowed.
For example, given the permutation [3, 6, 1, 2, 7, 8, 5, 4] (a permutation of the numbers from 1 to 2^{3}), the permutation can be sorted as follows:
Count how many ways there are to sort the given permutation by using the rules above. A way is an ordered sequence of swaps, and two ways are the same only if the sequences are identical.
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains a single integer N. The following line contains 2^{N} space-separated integers: a permutation of the numbers 1, 2, ..., 2^{N}.
For each test case, output one line containing "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 using the rules above.
1 ≤ T ≤ 200.
1 ≤ N ≤ 4.
1 ≤ N ≤ 12.
Input |
Output |
4 1 2 1 2 1 4 3 2 3 7 8 5 6 1 2 4 3 2 4 3 2 1 |
Case #1: 1 Case #2: 3 Case #3: 6 Case #4: 0 |
Points | Correct | Attempted |
---|---|---|
4pt | 25 | 25 |
12pt | 19 | 21 |