Trong một vũ trụ song song, mọi người phát cuồng vì việc sử dụng các con số là lũy thừa của hai. Họ đã định nghĩa một chiến thuật sắp xếp thú vị cho các hoán vị của các số từ \(1\) đến \(2^N\). Họ định nghĩa thao tác hoán đổi như sau:

• Một dãy số để hoán đổi là hợp lệ nếu và chỉ nếu nó là một dãy các số liền kề có kích thước \(2^k\), và vị trí bắt đầu của nó (vị trí của phần tử đầu tiên trong dãy) là bội số của \(2^k\) (với các vị trí được đánh chỉ số từ \(0\)).
• Một thao tác hoán đổi hợp lệ kích thước-k được định nghĩa bằng cách hoán đổi hai dãy số hợp lệ, phân biệt, mỗi dãy có kích thước \(2^k\).

Để sắp xếp hoán vị đã cho, bạn được phép sử dụng tối đa một thao tác hoán đổi cho mỗi kích thước \(k\), với \(k \in [0, N)\). Ngoài ra, lưu ý rằng việc hoán đổi một dãy với chính nó là không được phép.

Ví dụ, cho hoán vị \([3, 6, 1, 2, 7, 8, 5, 4]\) (một hoán vị của các số từ \(1\) đến \(2^3\)), hoán vị này có thể được sắp xếp như sau:

• \([3, 6, 1, 2, 7, 8, 5, 4]\): thực hiện một lần hoán đổi kích thước-2 cho các dãy \([3, 6, 1, 2]\) và \([7, 8, 5, 4]\).
• \([7, 8, 5, 4, 3, 6, 1, 2]\): thực hiện một lần hoán đổi kích thước-0 cho \([5]\) và \([3]\).
• \([7, 8, 3, 4, 5, 6, 1, 2]\): thực hiện một lần hoán đổi kích thước-1 cho \([7, 8]\) và \([1, 2]\).
• \([1, 2, 3, 4, 5, 6, 7, 8]\): hoàn thành.

Các bước trên đã sử dụng mỗi kích thước hoán đổi (\(0, 1\), và \(2\)) tối đa một lần. Ngoài ra, hãy chú ý rằng tất cả các lần hoán đổi đều hợp lệ vì cả hai dãy cho mỗi kích thước \(k\) đều bắt đầu tại các chỉ số là bội số của \(2^k\).

Hãy đếm xem có bao nhiêu cách để sắp xếp hoán vị đã cho bằng cách sử dụng các quy tắc trên. Một cách là một chuỗi các thao tác hoán đổi có thứ tự, và hai cách được coi là giống nhau chỉ khi các chuỗi đó đồng nhất.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Dòng đầu tiên của mỗi bộ test chứa một số nguyên duy nhất \(N\). Dòng tiếp theo chứa \(2^N\) số nguyên cách nhau bởi dấu cách: một hoán vị của các số \(1, 2, \dots, 2^N\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số cách sắp xếp hoán vị đã cho bằng các quy tắc trên.

Ràng buộc

• \(1 \le T \le 200\).

Phân nhóm

• Small dataset: \(1 \le N \le 4\).
• Large dataset: \(1 \le N \le 12\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Power Swapper.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.