거듭제곱 교환기

평행 우주에서는 사람들이 2의 거듭제곱인 수를 사용하는 데 열광하며, 1부터 $2^{N}$까지의 수로 이루어진 순열을 위한 흥미로운 정렬 전략을 정의했다. 이들은 교환 연산을 다음과 같이 정의했다.

• 교환할 수의 구간은 크기가 $2^{k}$인 연속한 수들의 구간이고, 그 시작 위치(구간의 첫 번째 원소의 위치)가 $2^{k}$의 배수일 때, 그리고 그럴 때에만 유효하다(위치는 0부터 번호를 매긴다).

• 크기 k의 유효한 교환 연산은 각각 크기가 $2^{k}$인 서로 다른 두 유효한 수의 구간을 맞바꾸는 것으로 정의한다.

주어진 순열을 정렬하기 위해, [0, N)에 속하는 각 k에 대해 크기 k의 교환 연산을 최대 한 번 사용할 수 있다. 또한 구간을 자기 자신과 맞바꾸는 것은 허용되지 않는다는 점에 유의한다.

예를 들어, 순열 $[3, 6, 1, 2, 7, 8, 5, 4]$(은)는 (1부터 $2^{3}$까지의 수로 이루어진 순열) 다음과 같이 정렬할 수 있다.

• $[3, 6, 1, 2, 7, 8, 5, 4]$: 구간 $[3, 6, 1, 2]$과 $[7, 8, 5, 4]$을 크기 2의 교환 연산으로 맞바꾼다.

• $[7, 8, 5, 4, 3, 6, 1, 2]$: $[5]$과 $[3]$을 크기 0의 교환 연산으로 맞바꾼다.

• $[7, 8, 3, 4, 5, 6, 1, 2]$: $[7, 8]$과 $[1, 2]$을 크기 1의 교환 연산으로 맞바꾼다.

• $[1, 2, 3, 4, 5, 6, 7, 8]$: 완료한다.

앞의 단계에서는 모든 교환 크기(0, 1, 2)를 각각 최대 한 번 사용했다. 또한 각 크기 k에 대한 두 구간이 모두 $2^{k}$의 배수인 인덱스에서 시작했으므로 모든 교환이 유효했다는 점에 유의한다.

위 규칙을 사용하여 주어진 순열을 정렬하는 방법의 수를 센다. 하나의 방법은 교환 연산들의 순서 있는 수열이며, 두 방법은 그 수열들이 동일할 때, 그리고 그럴 때에만 같다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 200.

소규모 데이터셋

시간 제한: 60초. 1 ≤ N ≤ 4.

대규모 데이터셋

시간 제한: 120초. 1 ≤ N ≤ 12.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N이 포함된다. 다음 줄에는 공백으로 구분된 $2^{N}$개의 정수, 즉 1, 2, ..., $2^{N}$의 순열이 주어진다.

각 테스트 케이스마다 "Case #x: y"이 포함된 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 위 규칙을 사용하여 주어진 순열을 정렬하는 방법의 수이다.