## KPGRAPHS - Counting Graphs

no tags

In this problem your task is to count the amount of graphs of different types. We only consider undirected graphs without self-loops. Every pair of vectices can be connected with at most one edge. Graphs are labeled, i.e. if a graph has N vertices, then each of them has a unique label from 1 to N.

We will be interested in three types of graphs - connected, eulerian and bipartite. A graph is connected, if and only if there is at least one path between any pair of vertices. A graph is eulerian, if and only if it's connected and there is a cycle that goes through every edge exactly once. A graph is bipartite, if and only if we can split all of its vertices into two subsets A and B, such that every edge has one endpoint in A and another in B.

### Input

The first line of the input contains one integer number T (1 <= T <= 1000) - the number of test cases.

Next T lines contain different test cases. Each test case contains one integer number N (1 <= N <= 1000) - the number of vertices in a graph.

### Output

For each test case, output the number of connected graphs, the number of euleran graphs and the number of bipartite graphs - all modulo 1000000007. See examples for the required format. Output one additional empty line after each test case.

### Example

`Input:212Output:Connected: 1Eulerian: 1Bipartite: 1Connected: 1Eulerian: 0Bipartite: 2` [Trichromatic] XilinX: 2013-02-28 15:06:58 A similar(but completely different) task is PT07D(Let us count 1 2 3).