Alleys Construction

In Andrei's city, people want to socialize as much as possible after the pandemic. The Fund for Providing the City (FPC) has announced that they want to construct alleys to create small social bubbles between households. An alley is a connection between two distinct houses. Each house must be connected with exactly one alley to another house within the same neighbourhood and the alleys may not intersect. Moreover, we know that the number of inhabitants of any neighbourhood will be even and the houses in each neighbourhood are arranged in a circle. The inhabitants want to find out, for each neighbourhood, in how many ways these alleys can be built. For example, in a neighbourhood that has six houses, there are five possible ways of constructing alleys, as shown in Figure A.1.

Figure A.1: For a neighbourhood of six houses, there are five possible ways of constructing alleys. Each black dot represents a house, and each line represents a possible alley.

Calculate in how many possible ways the inhabitants of Andrei's city could construct alleys in each neighbourhood. Because this number can be very high, the answer should be modulo $313109$.

The input consists of:

• A line with a single integer $q$ ($1\leq q\leq 10^4$), the number of neighbourhoods.
• $q$ lines, each containing one even number $n$ ($2\leq n\leq 10^{18}$), representing the number of the houses in the neighbourhood.

Output $q$ lines, each line containing one number: the number of possible ways in which alleys can be built in each neighbourhood. This number should be modulo $313109$.