2의 거듭제곱 구간 교환

평행 우주의 사람들은 2의 거듭제곱을 좋아해서, $1$ 부터 $2^N$ 까지의 순열을 제한된 교환 하나만으로 정렬한다. 위치는 $0$ 번부터 센다.

크기가 $k$ 인 올바른 구간은 연속한 위치 $2^k$ 개로 이루어지고 첫 위치가 $2^k$ 의 배수인 구간이다. 크기가 $k$ 인 교환은 서로 다른 두 올바른 구간의 내용을 통째로 맞바꾼다. 한 구간을 자기 자신과 맞바꿀 수는 없다.

순열을 정렬할 때 크기가 $k$ 인 교환은 $k = 0, 1, \dots, N-1$ 마다 최대 한 번씩만 쓸 수 있다.

예를 들어 $1$ 부터 $2^3$ 까지의 순열 [3, 6, 1, 2, 7, 8, 5, 4]는 다음처럼 정렬된다.

[3, 6, 1, 2, 7, 8, 5, 4]: 크기가 $2$ 인 교환으로 [3, 6, 1, 2]와 [7, 8, 5, 4]를 맞바꾼다.
[7, 8, 5, 4, 3, 6, 1, 2]: 크기가 $0$ 인 교환으로 [5]와 [3]을 맞바꾼다.
[7, 8, 3, 4, 5, 6, 1, 2]: 크기가 $1$ 인 교환으로 [7, 8]과 [1, 2]를 맞바꾼다.
[1, 2, 3, 4, 5, 6, 7, 8]: 정렬이 끝났다.

크기 $0$ , $1$ , $2$ 를 각각 최대 한 번씩만 썼고, 모든 구간이 자기 크기의 배수인 위치에서 시작했다.

이 규칙으로 주어진 순열을 정렬하는 방법의 수를 세어라. 한 방법은 교환을 순서대로 나열한 것이고, 나열이 완전히 같을 때만 두 방법이 같다.

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에 정수 $N$ 이 주어지고, 다음 줄에 $1, 2, \dots, 2^N$ 의 순열을 이루는 정수 $2^N$ 개가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 $1$ 부터 시작하는 테스트 케이스 번호이고, y는 주어진 순열을 정렬하는 방법의 수이다.