2의 거듭제곱 교환 (작은 입력)

어떤 평행 우주의 사람들은 2의 거듭제곱을 아주 좋아해서, 1부터 $2^N$까지의 순열을 정렬할 때 다음 교환 규칙만 쓴다.

• 연속한 수 $2^k$개로 이루어진 구간은 시작 위치가 $2^k$의 배수일 때만 올바른 구간이다. 위치는 0번부터 센다.
• 크기가 $k$인 교환은 길이가 모두 $2^k$인 서로 다른 두 올바른 구간을 맞바꾸는 연산이다.

순열을 정렬할 때 $0 \le k < N$인 각 $k$마다 크기가 $k$인 교환을 최대 한 번 쓸 수 있다. 같은 구간끼리 맞바꾸는 것은 허용하지 않는다.

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

• $[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를 각각 최대 한 번씩 썼고, 맞바꾼 구간은 모두 시작 위치가 자기 길이의 배수였다.

위 규칙으로 주어진 순열을 정렬하는 방법의 수를 세어라. 방법 하나는 교환을 순서대로 늘어놓은 나열이고, 두 방법은 나열이 완전히 같을 때만 같은 방법이다. 순열이 이미 정렬되어 있으면 교환을 한 번도 하지 않는 빈 나열도 방법 하나로 센다.

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

제한

• $1 \le T \le 200$
• $1 \le N \le 4$

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