A un fuster danès anomenat Ole Kirk Christiansen el va afectar tant la Gran Depressió dels anys XX del segle passat que va passar de fer mobles a fer joguines de fusta. D'aquesta forma va obrir un negoci que un parell d'anys més tard va passar a dir-se LEGO com un acrònim de l'expressió danesa Leg godt (jugar bé). Amb els problemes d'abastiment de fusta després de la II Guerra Mundial va a començar a fer servir plàstic, i el 1949 va fabricar totxos de plàstic per fer construccions. No va ser fins al 1958 que van patentar un sistema amb els que els totxos s'enganxaven els uns als altres per sota. La resta de la història ja la coneixeu...

Vols construir una peça de Lego enorme fent servir les peces de Lego que tens disponibles. Les peces estàndard són de mida 1, 2, 3, 4, 6, 8 o 10 i tens infinites peces de cadascuna d'aquestes mides. El teu propòsit és fer una peça de la longitud que et demanin enganxant-les amb pega l'una amb l'altra. Però no només això, t'has proposat de fer-ne tantes com combinacions de peces puguis fer. De quantes formes diferents pots fer una peça d'una longitud determinada?

Entrada

L'entrada consta d'una primera línia amb un enter N que indica el nombre de casos. A continuació venen N línies, una per cada cas, amb la longitud que es vol aconseguir. La longitud serà sempre menor de 64.

Sortida

Per cada cas has de donar el nombre de combinacions diferents amb la qual es pot aconseguir la longitud desitjada. Recorda que, com que tenim infinites peces de longitud 1, totes les longituds es poden aconseguir.

Exemple d'Entrada

5
1  
2
3
4
10

Exemple de Sortida

1
2
4
8
435