Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

KOLKO - Kołko graniaste

no tags 

W specjalizowanym przedszkolu dla artystycznie uzdolnionych dzieci we wtorki odbywają się zajęcia z kolorowania kółek graniastych. Na ile sposobów może zostać pomalowane n-kąciaste kółko graniaste, jeżeli z powodu światowego kryzysu dziecko ma do dyspozycji tylko dwa kolory?

Kółko graniaste, 6-kąciaste

Kółko graniaste n-kąciaste ma kształt n-kątu foremnego, podzielonego na sektory przez odcinki, łączące środek z wierzchołkami. Na rysunku jest pokazane kółko graniaste, 6-kąciaste. Każdy z sektorów powinien zostać pomalowany. Dwa kółka graniaste n-kąciaste są pomalowane na ten sam sposób, jeżeli jedno z nich może zostać otrzymane z drugiego obrotem.

Input

W pierwszej linii podana jest liczba całkowita L (1≤ L≤ 10) ilość zestawów danych. Każdy zestaw składa się z jednej linijki, w której podana jest liczba całkowita n (1≤ n≤ 24) ilość sektorów kółka graniastego.

Output

Dla każdego zestawu wejściowego należy wypisać po jednej w linijce liczbę całkowitą K(n) --- ilość różnych sposobów pokolorować kółko graniaste n-kąciaste.

Example

Input:
2
1
3

Output:
2
4

Added by:Aleksander Denisiuk
Date:2011-11-28
Time limit:1.076s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64