홍준이의 친위대

홍준 왕국의 국왕 홍준이에게는 자신을 호위하는 $N$명의 친위대 병사가 있다. 병사들의 키는 모두 다르다. 홍준이는 병사들을 일렬로 세울 때, 양 끝의 두 병사를 제외한 나머지 각 병사에 대해 그 양옆에 선 두 병사의 키가 모두 자기보다 크거나 모두 자기보다 작으면 그 배치를 보기 좋다고 생각한다.

예를 들어 키가 서로 다른 7명의 병사가 있고 키가 각각 160, 162, 164, 166, 168, 170, 172cm라고 하자. 이들을 166 172 164 170 160 168 162 순서로 세우면, 양 끝을 뺀 모든 병사의 양옆이 자기보다 모두 크거나 모두 작으므로 홍준이는 이 배치를 보기 좋다고 생각한다.

홍준이는 매일 같은 배치를 보면 지루해하므로, 매일 새로운 보기 좋은 배치를 만들고 싶어 한다. 즉, 병사가 $N$명일 때 서로 다른 보기 좋은 배치가 몇 가지인지 알고 싶다.

예를 들어 병사가 4명이고 편의상 키를 1, 2, 3, 4로 나타내면, 보기 좋은 배치는 다음 10가지이다.

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

병사의 수 $N$이 주어졌을 때, 가능한 보기 좋은 배치의 수를 구하는 프로그램을 작성하시오.

첫 줄에 테스트케이스의 수 $T$가 주어진다 ($1 \le T \le 1{,}000$).

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

각 테스트케이스에 대해 가능한 보기 좋은 배치의 수를 한 줄에 하나씩 출력한다.