时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld
题目描述
There was a magic necklace. The necklace is made of magical gems numbered 1 through n. Unfortunately, the necklace was accidentally broken yesterday. Every gem was scattered on the ground.
Now you need to restring the magic necklace with these n gems. In order to keep the necklace magical, adjacent numbered gems cannot be placed next to each other in the new necklace.
Please output the number of ways to successfully restring the necklace.
If the relative positions of the gems are the same, we think these are the same case.
输入描述:
The first line of the input contains one integer t — the number of test cases.(t ≤ 110)The next t lines contain test cases. Each line contains a positive integer n（0 ≤ n ≤ 11）describing a test case.
输出描述:
For each test case, output a line containing an integer which indicates the answer.
