Counting Derangements

In this problem, you are given a non-negative integer (n) and you need to compute the number of derangements, also known as subfactorials (!n). A derangement is a permutation of the elements of a set, such that no element appears in its original position. The recurrence relation for computing the number of derangements (D(n)) is given by: [ D(n) = (n - 1) \times (D(n - 1) + D(n - 2)) ] with base cases (D(0)=1) and (D(1)=0). Your task is to answer multiple test cases using this formula.

inputFormat

The input consists of multiple lines. The first line contains an integer (T) representing the number of test cases. Each of the next (T) lines contains one non-negative integer (n).

outputFormat

For each test case, print a single line containing the number of derangements (D(n)).## sample

3
1
2
3

0
1
2