Бджола, що тільки що появилась із личинки, вирішила поподорожувати по сотах. На кожному "кроці" бджола може переміститись в одну із сусідніх комірок і через n кроків повинна знову повернутись у комірку, з якої почала свою подорож.

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

Вхідні дані

Перший рядок містить кількість тестів. Кожен тест розміщено в окремому рядку та містить одне ціле число n (1 ≤ n ≤ 14).

Вихідні дані

Для кожного тесту вивести в окремому рядку шукану кількість можливих прогулянок. Выдомо, що відповідь не перевищує 231.