Обчислити знову?#6013
Для заданого цілого числа потрібно обчислити кількість способів, якими можна заповнити прямокутник розміром 4 \times n плитками розміром 3 \times 1.
Оскільки результат може бути дуже великим, виведіть залишок від ділення цього результату на .
Перший рядок містить кількість тестів (1 \le t \le 100). Кожен тест представлений одним рядком, що містить одне ціле число (1 \le n \le 10000).
Для кожного тесту виведіть відповідь в окремому рядку, взяту за модулем .
Приклад 1