On se donne un entier n. Le graphe du n-hypercube est le graphe formé par les sommets et côtés du n-hypercube. Le n-demihypercube est le polytope de dimension n formé en alternant les sommets du n-hypercube. Ainsi le graphe du n-demihypercube correspond au graphe formé en connectant les sommets à distance 2 (autrement dit, la moitié bipartie du graphe du n-hypercube). Le processus de construction n’a que peu d’importance puisque deux n-demihypercube construits à parti du même n-hypercube sont évidemment isomorphes.

Néanmoins on pourra rappeler que le graphe du n-demihypercube peut être vu est assez trivialement (il suffit, bien sûr, de revenir à l’intuition géomètrique du n-demihypercube) comme le carré du (n-1)-hypercube.

De même, une clique est un sous-ensemble de sommets dont le graphe induit est complet. Une clique est dite maximum si son cardinal est un maximum pour l’ensemble des cliques du graphe considéré.

Étant donné une dimension n, donner le nombre de cliques maximums du graphe du n-demihypercube.

Input

N cas

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

Exemples

Faites un dessin.