Problem T: Fetching Stones

Problem T: Fetching Stones

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 46  Solved: 21
[Submit][Status][Web Board]

Description

There are \(n\) stones in a line, and we are going to fetch one away in each operation, so after \(n\) operations the stones are all fetched away. In the first operation, we can fetch any one of the \(n\) stones. But in later operations, only those stones, which have at least one adjacent stone already fetched, can be fetched. For example, assuming there are \(n=5\) stones and we fetch the \(3\)-rd stone in the first operation, then we can only fetch the \(2\)-nd or the \(4\)-th stone in the second operation. Do you know how many different schemes there are to fetch all the stones? Two schemes are different if there exists one operation in which different stones are fetched.


Input

The first line contains an integer \(T\), representing the number of test cases.

Then \(T\) lines follow. Each line contains an integer \(n\) for a test case.

\(0<n\leq 100;\)

Output

Output \(T\) lines. The \(i\)-th line contains an integer which is the number of schemes to fetch stones modulo \(20140413\) in the \(i\)-th test case.

Sample Input

2
1
2

Sample Output

1
2

HINT

[Submit][Status]