Description

在一个平行宇宙里，人们痴迷于使用 $2$ 的幂次方，并且他们为从 $1$ 到 $2^{\mathrm{N}}$ 的数列定义了一种激动人心的排序方式。这里定义的交换操作如下：

• 一段可交换的区间是指一个长度为 $2^{k}$ 的连续区间，并且其起始位置（从 $0$ 开始计数）必须是 $2^{k}$ 的倍数。
• 一次合法的 $k$ 级交换操作是指交换两个不同的、各自合法的长度为 $2^{k}$ 的区间。

为了将一个给定的排列排序为升序排列，你最多可以对每个 $k \in [0, N)$ 使用一次这样的交换操作。注意，不允许交换一个区间与其自身。

例如，对于排列 $[3,6,1,2,7,8,5,4]$（即 $1$ 到 $2^3=8$ 的一个排列），可以按如下步骤排序：

1. $[3,6,1,2,7,8,5,4]$：执行一次 size-2 的交换，交换区间 $[3,6,1,2]$ 与 $[7,8,5,4]$。
2. $[7,8,5,4,3,6,1,2]$：执行一次 size-0 的交换，交换 $[5]$ 和 $[3]$。
3. $[7,8,3,4,5,6,1,2]$：执行一次 size-1 的交换，交换 $[7,8]$ 与 $[1,2]$。
4. $[1,2,3,4,5,6,7,8]$：排序完成。

上面每一种 size 的交换操作最多只使用了一次。同时，每次交换都满足合法性：两个长度为 $2^k$ 的区间起始位置均为 $2^k$ 的倍数。

现在请你计算，将给定排列按上述规则排序，有多少种不同的方式？每一种方式是一个有序的交换序列，只有当两种方式的交换序列完全一致时，才认为它们相同。

Input Format

输入的第一行是测试用例数 $\mathrm{T}$。接下来是 $\mathrm{T}$ 个测试用例。

每个测试用例的第一行是一个整数 $\mathrm{N}$，表示排列的大小为 $2^{\mathrm{N}}$。

下一行是 $2^{\mathrm{N}}$ 个用空格分隔的整数，表示一个 $1$ 到 $2^{\mathrm{N}}$ 的排列。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是将给定排列按题目要求排序的不同方法数。

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

Hint

限制条件

• $1 \leq \mathrm{T} \leq 200$

Small 数据集（4 分）

• 时间限制：60 3 秒
• $1 \leq \mathrm{N} \leq 4$

Large 数据集（12 分）

• 时间限制：120 5 秒
• $1 \leq \mathrm{N} \leq 12$

翻译由 ChatGPT-4o 完成