Az azonosító címkeként egy n hosszú csempe kódot szeretnénk használni, ami 1×2, 2×1, és 2×2 méretű csempéket tartalmaz egy 2×n méretű négyzetrácson. Lefedéskor a négyzetrács minden mezőjét pontosan egy csempének kell fednie. (A csempék között nem lehet átfedés, és nem lehet fedetlen mező.)
Az ábrákon az 5 hosszúságú négyzetrács és egy hozzá tartozó csempe kód látható. Nem tekintünk különbözőnek két kódot, ha egymás megfordítottjai. A 2. és 3. ábrán látható lefedések tehát megegyezőnek számítanak.
Adott pozitív n esetén adjunk programot, ami kiszámítja, hogy hány különböző n hosszú csempe kód létezik, vagyis a négyzetrács hányféleképpen fedhető le a fent megadott módon.
A bemenetben első sorában adott T, a tesztesetek száma. Az ezt követő T sorban egy pozitív n egész szám van megadva, a tesztesethez tartozó négyzetrács nagysága. (3 ≤ n ≤ 30)
A kimenet T sort tartalmazzon, minden egyes tesztesethez a különböző kódok számát.
| INPUT | OUTPUT |
|---|---|
2 3 4 |
3 8 |
(ACM feladat nyomán)