2 x n ölçülü düzbucaqlını triominolarla neçə üsulla qapamaq mümkündür? Aşağıda təsvir olunmuş ilk iki həndəsi fiqur \textbf{triomino} adlanır (başqa cür triomino mövcud deyil) Göründüyü kimi, \textbf{triomino} - üç ədəd \textbf{1 x 1} ölçülü kvadratik tərəf birləşməsi ilə əmələ gəlir: \includegraphics{https://static.e-olymp.com/content/12/12088b401e5e009ceb3d1173a855103dff63b597.jpg} Məsələn, \textbf{2 × 3 ölçülü düzbucaqlını üç müxtəlif üsulla qapamaq olar (yuxarıda təsvir olunmuş son üç forma).} Cavabın kifayət qədər böyük ola biləcəyini nəzərə alaraq, Siz üsullar sayının \textbf{10^6}-ya görə modulunu tapsanız kifayətdir. \InputFile Birinci sətirdə testlər sayını göstərən \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}) ədədi verilir. Sonrakı \textbf{T} sətirdə isə,\textbf{ n} (\textbf{0} < \textbf{n} < \textbf{10^9}) ədədinin müvafiq testə uyğun qiyməti sadalanır. \OutputFile \textbf{T} sətirdə, müvafiq test üçün \textbf{2 × n} ölçülü düzbucaqlını qapamaq üçün mümkün olan üsullar sayının \textbf{10^6}-ya görə modulu verilir.