Let’s consider an integer n. The graph of the n-hypercube is the graph formed with the vertices and edges of the n-hypercube. The n-demihypercube is the polytope of dimension n formed by alterning the vertices fo the n-hypercube. Therefore the graph of the n-hypercube coincides with the graph formed by connecting the vertices at distance 2 ( i.e., the half bipartite graph of the n hypercube). The porcess of constructing it is only of little importance as two n-hypercubes constructed from the same n-hypercube are evidently isomorphic.

However, we will remind the reader that the graph of the n-hypercube can be seen rather trivially (you simply have to go back the geometric intuition of the n-demihypercube) as the square of the (n-1)-hypercube.

Likewise, a clique is a subset of the vertices of which the graph induced is complete. A clique must be said maximal if its cardinality is a maximum for the set of the cliques of the considered graph.

Given a dimension n, give the number of maximal cliques of the graph of the n-demihypercube.

Input

N cas

• 4 ≤ n ≤ 60
• 10 ≤ N ≤ 15

Examples

Draw something.