Скількома способами ви можете замостити прямокутник \textbf{2 × n} триміношками? Триміно -- це геометрична фігура, складена з трьох квадратів, що з'єднуються між собою вздовж повного ребра. Є тільки дві можливих триміношки: \includegraphics{https://static.e-olymp.com/content/12/12088b401e5e009ceb3d1173a855103dff63b597.jpg} Наприклад, замостити прямокутник \textbf{2 × 3} можна лише трьома різними способами. Оскільки відповідь може бути достатньо великою, шукану кількість способів слід обчислювати за модулем \textbf{10^6}. \InputFile Перший рядок містить кількість тестів \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{100}). Кожний з наступних \textbf{t} рядків містить значення \textbf{n} (\textbf{0} < \textbf{n} < \textbf{10^9}). \OutputFile Для кожного тесту в окремому рядку виведіть кількість способів, якими можна замостити прямокутник \textbf{2 × n}. Результат слід виводити за модулем \textbf{10^6}.