Süticsomagolás

Wolfgang Pucknak van két jellegzetes szokása:

1. Csak kétféle alakú süteményt készít. Az egyik négyzet alakú, amelynek a területe egy egység. A másik L alakú, és 3 egység a területe.
2. Csak meghatározott méretű dobozokba csomagolva szállítja a süteményeket. A dobozok mindig 2 egység szélesek és változó hosszúak.

A minap Wolfgang azon morfondírozott, hogy hányféleképpen tudja becsomagolni a süteményeit adott méretű dobozokba. Tudnál neki segíteni?

A Wolfgang által készített sütemények pontos mérete, illetve egy 6 egység hosszúságú dobozba történő becsomagolásuknak egy lehetséges módja.

Egy 2 egység hosszúságú doboz megtöltésének 5 lehetséges módja.

A bemenet specifikációja

A bemenet t-vel, a különböző dobozhosszúságok számával kezdődik. A következő t sor mindegyike egy-egy n egész számot tartalmaz (1 ≤ n ≤ 40).

A kimenet specifikációja

Minden n esetén egyetlen egész számot kell a kimenetre írni külön sorban, amely megadja, hogy hányféleképpen lehet megtölteni egy 2 × n méretű dobozt a fent leírt süteményekkel. A kimenet garantáltan kisebb lesz, mint 10¹⁸.

Példa bemenet

1. 2
2. 1
3. 2

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 1
2. 5

letöltés szöveges állományként