시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 345 176 123 47.308%

문제

RUNIST 대학교에서는 매 학기마다 재미있는 기숙사 배정을 한다.

RUNIST 대학교에는 N명의 학생이 있고 N개의 기숙사가 있다. 모든 N명의 학생들은 봄학기에 기숙사를 한명 당 하나씩 배정을 받았고, 모두 각각 다 다른 기숙사에 배정이 되었다.

이제 가을학기가 되어 학생복지팀에서는 기숙사를 다시 배정하려고 한다. 모든 학생들은 본인이 살았던 봄학기 기숙사에서 가을 학기에 다른 기숙사로 배정되면 이사를 해야하므로 기숙사 재배정을 신청하였다. (기숙사 재배정이 된다면 기숙사를 그대로 쓰게 된다.)

이렇게 모든 학생들은 기숙사 재배정을 신청했지만, 학생복지팀에서는 어떤 학생에게도 기숙사 재배정을 해주지 않으려고 한다.

봄학기때 기숙사를 이미 배정받은 상태에서, 가을학기 기숙사에 아무도 재배정이 되지 않는 경우의 수를 구해보자.

입력

첫번째 줄에 테스트 케이스의 수 T가 주어진다.

각 케이스의 첫번째 줄에 학생 명수(기숙사의 개수) N (1 ≤ N ≤ 20) 이 주어진다. 

출력

각 테스트 케이스 별로 아무도 재배정이 되지 않는 경우의 수를 출력한다.

예제 입력

2
3
4

예제 출력

2
9

힌트

N이 4인 경우, 봄학기 때 4명의 학생 (민수, 동화, 갑도, 석주)이 각각 기숙사 A,B,C,D에 배정이 되었다면,

(민수-B, 동화-A, 갑도-D, 석주-C), (민수-B, 동화-C, 갑도-D, 석주-A), (민수-B, 동화-D, 갑도-A, 석주-C), (민수-C, 동화-A, 갑도-D, 석주-B), (민수-C, 동화-D, 갑도-A, 석주-B), (민수-C, 동화-D, 갑도-B, 석주-A), (민수-D, 동화-A, 갑도-B, 석주-C), (민수-D, 동화-C, 갑도-A, 석주-B), (민수-D, 동화-C, 갑도-B, 석주-A)

다음과 같은 9가지 경우가 존재한다.