Dormitory Reassignment

Time limit1sMemory limit128 MB

Summary

Count the permutations of N students to rooms in which no student keeps the same room.

Level: Medium4 of 10
Topics: Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

RUNIST University assigns dormitory rooms again every semester.

There are $N$ students and $N$ dormitory rooms. In the spring semester each of the $N$ students received a different room.

The autumn semester has come and the student welfare team assigns the rooms again. In the autumn semester each student again uses one room, and different students use different rooms.

A student who keeps the same room in autumn that they used in spring is called a reassigned student. Every student applied for reassignment, but the student welfare team wants no student to be reassigned.

The spring assignment is fixed. Count the autumn assignments in which no student is reassigned.

Input

The first line contains the number of test cases $T$ .

Each of the following test cases is given on one line and contains $N$ ( $1 \le N \le 20$ ), the number of students and also the number of rooms.

Output

For each test case, print on its own line the number of assignments in which no student is reassigned.

Hint

Let $N = 4$ and suppose that in spring Minsu, Donghwa, Gapdo and Seokju received rooms A, B, C and D in that order. The autumn assignments with no reassigned student are these 9.

(Minsu: B, Donghwa: A, Gapdo: D, Seokju: C), (Minsu: B, Donghwa: C, Gapdo: D, Seokju: A), (Minsu: B, Donghwa: D, Gapdo: A, Seokju: C), (Minsu: C, Donghwa: A, Gapdo: D, Seokju: B), (Minsu: C, Donghwa: D, Gapdo: A, Seokju: B), (Minsu: C, Donghwa: D, Gapdo: B, Seokju: A), (Minsu: D, Donghwa: A, Gapdo: B, Seokju: C), (Minsu: D, Donghwa: C, Gapdo: A, Seokju: B), (Minsu: D, Donghwa: C, Gapdo: B, Seokju: A)

Examples3

Example 1
Input
```
2
3
4
```
Expected output
```
2
9
```
Example 2
Input
```
1
1
```
Expected output
```
0
```
Example 3
Input
```
1
2
```
Expected output
```
1
```