POLSKI SPOJ

W Bajtocji nadszedł dzień Święta Wojska Bajtockiego. Pan Bajteusz postanowił wywiesić przed domem flagę swej ojczyzny. Jest tylko jeden mały problem. Otóż Bajtocja nie posiada flagi jako takiej... Flagą Bajtocji nazwiemy dowolną flagę złożoną z pionowych pasków o kolorze czerwonym, zielonym lub niebieskim oraz czarnej obwódce, spełniającą podane warunki:

1. Dwa paski o tym samym kolorze nie mogą ze sobą sąsiadować.

2. Pasek w kolorze niebieskim musi znajdować się bezpośrednio pomiędzy paskami z których jeden ma kolor zielony, a drugi - czerwony (czyli niepoprawną flagą jest CZNZ).

Pan Bajteusz chciałby wiedzieć ile jest możliwych flag Bajtocji o podanej długości - w ten sposób będzie wiedział, czy uda mu się wywiesić je wszystkie.

Wejście

Wejście rozpoczyna liczba testów 1 ≤ t ≤ 500 000. Następnie każdy test w oddzielnej linii. Pojedynczy test składa się z jednej liczby całkowitej 1 ≤ n ≤ 10⁶.

Wyjście

Dla każdego testu odpowiedź w oddzielnej linii - liczba możliwych flag Bajtocji składających się z n pasków modulo 10¹⁵.

Przykład

Wejście:
1
3

Wyjście:
4

Wyjaśnienie do przykładu:
Są 4 takie flagi: RGR, GBR, RBG, GRG