Бджола, що тільки що появилась із личинки, вирішила поподорожувати по сотах. На кожному "кроці" бджола може переміститись в одну із сусідніх комірок і через n кроків повинна знову повернутись у комірку, з якої почала свою подорож.
Ваша програма повинна для заданого n
визначити кількість можливих прогулянок бджоли.
Перший рядок містить кількість тестів. Кожен тест розміщено в окремому рядку та містить одне ціле число n (1 ≤ n ≤ 14).
Для кожного тесту вивести в окремому рядку шукану кількість можливих прогулянок. Выдомо, що відповідь не перевищує 2^31
.