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 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