기숙사 재배정

RUNIST 대학교는 학기마다 기숙사를 새로 배정한다.

학생은 $N$명이고 기숙사도 $N$개다. 봄학기에 $N$명은 서로 다른 기숙사를 하나씩 배정받았다.

가을학기가 되어 학생복지팀이 기숙사를 다시 배정한다. 가을학기에도 학생 한 명이 기숙사 하나를 쓰고, 서로 다른 학생은 서로 다른 기숙사를 쓴다.

봄학기에 쓰던 기숙사를 가을학기에도 그대로 쓰게 되는 학생을 재배정된 학생이라고 한다. 모든 학생이 기숙사 재배정을 신청했지만, 학생복지팀은 어느 학생도 재배정하지 않으려고 한다.

봄학기 배정이 정해져 있을 때, 재배정된 학생이 한 명도 없는 가을학기 배정의 경우의 수를 구하라.

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

이어서 각 테스트 케이스마다 한 줄에 학생 수이자 기숙사 수인 $N$ ($1 \le N \le 20$)이 주어진다.

각 테스트 케이스마다 재배정된 학생이 한 명도 없는 배정의 경우의 수를 한 줄에 하나씩 출력한다.

$N = 4$이고 봄학기에 민수, 동화, 갑도, 석주가 각각 기숙사 A, B, C, D를 배정받았다고 하자. 재배정된 학생이 한 명도 없는 가을학기 배정은 다음 9가지다.

(민수: 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)