Только что появившаяся из личинки пчела решила попутешествовать по сотах. На каждом "шагу" пчела может переместится в одну из соседних ячеек и через n шагов должна новь возвратиться в ячейку, с которой начала своё путешествие.

Ваша программа должна определить для заданного n количество возможных прогулок пчелы.

Входные данные

Первая строка содержит количество тестов. Каждый тест расположен в отдельной строке и содержит одно целое число n (1 ≤ n ≤ 14).

Выходные данные

Для каждого теста вывести в отдельной строке искомое количество возможных прогулок. Известно, что ответ не превышает 231.