- Time limit: 5.00 s
- Memory limit: 256 MB
Kaaleppi has created the following puzzle:
Given an integer , construct a permutation of numbers such that there are no adjacent values whose difference is .
For example, when , there are solutions: and .
Your task is to calculate the number of solutions for Kaaleppi's puzzle for given values. The answer may be big so please output it modulo .
Input
The first input line contains an integer : the number of test cases.
After this, lines follow. Each line contains an integer .
Output
For each test case, output the number of solutions for Kaaleppi's puzzle modulo .
Constraints
Example
Input:
3 4 9 123
Output:
2 47622 554938841