홍준이의 친위대

홍준 왕국의 국왕 홍준이는 자신을 호위하는 N명의 친위대 병사가 있다. 병사들의 키는 모두 다르다. 홍준이는 그들을 일렬로 세울 때, 키 순서대로 세우는 것보다 맨 끝 두 병사를 제외한 나머지 병사들의 양 옆 두 병사의 키가 자신 보다 크거나 모두 자신보다 작을 때 보기 좋다고 생각한다. 예를 들어, 홍준이에게 7명의 친위대 병사가 있고, 그 들의 키가 160, 162, 164, 166, 168, 170, 그리고 172cm 라고 하자. 아래와 같이 병사가 일렬로 서있으면 홍준이는 보기 좋다고 생각한다.

만약 홍준이가 매일 같은 병사 배치를 본다면 매우 지루해할 것이다. 때문에 매일 병사들의 배치를 새롭게 하고 싶다. 즉, 병사 N명이 있을 때 서로 다른 배치가 몇 가지 있는지 알고 싶어한다.

예를 들어, 병사가 4명이 있고 편의상 그들의 키를 1, 2, 3, 4라고 나타내자. 그러면 아래와 같이 10가지 배치가 가능하다.

1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423

병사의 수 N이 주어졌을 때, 가능한 배치의 수를 구하는 프로그램을 작성하자.

첫 줄에 테스트케이스 수 T가 주어진다. (1 ≤ T ≤ 1,000)

각 테스트케이스마다 병사의 수를 나타내는 자연수 N이 주어진다. (1 ≤ N ≤ 20)

각 테스트케이스 마다 가능한 배치의 수를 줄로 구분하여 출력한다.