Hi havia una vegada un rei molt arrogant que no tractava gens bé els seus súbdits. Aquest rei, era poderós i ric, però no era feliç i s’avorria molt. Després de pensar moltíssim sobre què podia fer per trobar alguna cosa que el divertís, va creure que la solució seria convocar un concurs de jocs nous, i va dir que la persona que inventés el joc que li agradés més podria demanar-li el que volgués i ell li ho donaria.

Molta gent es va presentar al concurs, però el joc que més va agradar al rei va ser el que va presentar Sissa, un savi que va voler inventar un joc on el rei fos molt important però que sense l’ajuda de les altres peces no pogués guanyar mai. Sissa volia que el rei s’adonés de la importància de les altres peces del joc, les quals era com si fossin les persones del seu regne. I aquest va ser el primer joc d’escacs.

El rei va pensar que amb aquest joc podia fer moltes partides i que sempre serien diferents, i això li va agradar moltíssim perquè segur que no s’avorriria! Llavors, va voler complir la seva part del tracte i, tot fanfarró, li va dir a Sissa que demanés el que volgués. Sissa va dir-li que abans de dir una cosa s’ha d’estar segur que es podrà complir i el rei, tot presumit li va dir: “és clar, jo sóc molt ric i podré donar-te el que em demanis!”.

Sissa va dir-li: “d’acord, doncs vull que em doneu 1 gra de blat per la primera casella del tauler, 2 per la segona, 4 per la tercera, 8 per la quarta, i així fins arribar a la casella 64, l'ultima del tauler”.

Al rei li va agafar un atac de riure i va pensar: "quin savi més ruc! Podria demanar-me riqueses i em demana uns quants grans de blat!!!", i va dir als seus criats que li preparessin els sacs de blat.

Al cap d’una estona, un dels criats va venir corrents i amb cara de preocupat. Quan el rei li va preguntar què li passava, aquest li va respondre: “majestat, se’ns ha acabat el blat i no en tindrem prou en tot el reialme per satisfer el desig de Sissa”. Necessitaven 18.446.744.073.709.551.615 grans de blat!

Aquest problema s'ha de fer amb recursivitat

Entrada

La primera línea serà un nombre que diu quants casos de prova hi ha Cada cas compta amb un sol nombre, quantes caselles té el joc d'escacs

Sortida

La quantitat de grans de blat que s'han de donar. Feu servir longs per donar la resposta

Exemple d'Entrada

4
1
4
6
10

Exemple de Sortida

1
15
63
1023