Триміно

Скількома способами ви можете замостити прямокутник 2 × n триміношками? Триміно – це геометрична фігура, складена з трьох квадратів, що з'єднуються між собою вздовж повного ребра. Є тільки дві можливих триміношки:

Наприклад, замостити прямокутник 2 × 3 можна лише трьома різними способами. Оскільки відповідь може бути достатньо великою, шукану кількість способів слід обчислювати за модулем 10^6.

Вхідні дані

Перший рядок містить кількість тестів t (1 ≤ t ≤ 100). Кожний з наступних t рядків містить значення n (0 < n < 10^9).

Вихідні дані

Для кожного тесту в окремому рядку виведіть кількість способів, якими можна замостити прямокутник 2 × n. Результат слід виводити за модулем 10^6.

Приклади