In how many ways can you tile a \textbf{2 × n} rectangle with triominoes? A triomino is a geometric shape made from three squares joined along complete edges. There are only two possible triominoes: \includegraphics{https://static.e-olymp.com/content/12/12088b401e5e009ceb3d1173a855103dff63b597.jpg} For example, you can tile a \textbf{2 × 3} rectangle only in \textbf{3} different ways. As the answer can be quite big, you just need to find the number of ways modulo \textbf{10^6}. \InputFile The first line contains the number of test cases \textbf{t} (\textbf{1 ≤ t ≤ 100}). Each of the following \textbf{t} lines contains the value of \textbf{n} (\textbf{0 < n < 10^9}). \OutputFile For each test case print in a separate line a number of ways you can tile a \textbf{2 × n} rectangle. Print the answer modulo \textbf{10^6}.