보도블록 깔기

퀜도르에서는 보도와 복도의 폭이 언제나 $2$mb로 고정되어 있다. mb는 미니블로이트를 줄인 단위로, $1$블로이트의 약 $1/2000$이다. 은행마다 새 보도를 깔기로 한 J. 피어폰트 플랫헤드는 공사를 프로보즈 매직 페이버 사에 맡기면서 무늬를 직접 고르겠다고 했다. 보도가 워낙 많아서 프로보즈는 보도 하나를 빈틈없이 덮는 방법을 모두 세는 프로그램부터 만들기로 했다.

쓸 수 있는 블록은 세 종류다.

• 한 변이 $1$mb인 정사각형 블록
• $2$mb 곱하기 $1$mb 직사각형 블록, 가로와 세로 두 방향 모두 놓을 수 있다
• 직각 트로미노, 즉 L자 블록, 네 방향 모두 놓을 수 있다

블록은 보도 밖으로 나갈 수 없고 서로 겹칠 수도 없으며, 보도의 모든 칸이 정확히 한 블록에 덮여야 한다. 블록을 놓은 자리가 한 곳이라도 다르면 서로 다른 방법으로 센다.

예를 들어 $2 \times 1$ 보도를 덮는 방법은 $2$가지이고, 두 방법에서 쓰인 블록을 모두 합하면 $1 \times 1$ 정사각형 $2$개와 $2 \times 1$ 직사각형 $1$개다.

$2 \times 2$ 보도를 덮는 방법은 $11$가지이고, 열한 방법에서 쓰인 블록을 모두 합하면 $1 \times 1$ 정사각형 $16$개, $2 \times 1$ 직사각형 $8$개, 트로미노 $4$개다.

세로 $2$mb, 가로 $n$mb인 보도의 길이 $n$이 주어진다. 이 보도를 덮는 방법의 수와, 그 모든 방법에서 쓰인 블록의 종류별 총 개수를 구하는 프로그램을 작성하라. 종류별 개수는 방법 하나가 아니라 모든 방법에 걸쳐 더한 값이다.

첫째 줄에 데이터 집합의 개수 $P$가 주어진다. ($1 \le P \le 10\,000$)

다음 $P$개 줄에는 데이터 집합이 한 줄에 하나씩 주어진다. 각 줄에는 데이터 집합 번호 $K$와 보도의 길이 $n$이 공백 하나를 사이에 두고 주어진다. ($1 \le K \le 10\,000$, $1 \le n \le 14$)

데이터 집합은 서로 독립이며 모두 같은 방식으로 처리한다. $n$의 상한은 다섯 개의 출력 값이 모두 부호 없는 $32$비트 정수 범위에 들어가도록 정해진 값이다.

데이터 집합마다 한 줄씩 정수 다섯 개를 공백 하나로 구분해 출력한다. 차례대로 데이터 집합 번호 $K$, $2 \times n$ 보도를 덮는 방법의 수, 그 방법들에서 쓰인 $1 \times 1$ 정사각형의 총 개수, $2 \times 1$ 직사각형의 총 개수, 트로미노의 총 개수다.