Триомино

Сколькими способами можно замостить прямоугольник 2 × n триоминошками? Триомино - это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

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

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

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

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

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

Примеры