== include(page="template/taskheader" task_id="spatiu") ==
Poveste şi cerinţă...
Bulbuka sa urcat intro racheta si sa pierdut intrun spatiu bidimensional infinit. Pana ca cei de la Houston sa afle ca exista o problema, Bulbuka a si apucat sa se miste de N ori. Tot ce stiu in momentul asta este ca racheta a pornit de la coordonatele (0,0) si ca in fiecare moment racheta poate sa se miste din orice punct doar in cele 4 directii alaturate de coordonate intregi (de exemplu: (0, 0) > (0, 1) sau (0, 1) sau (1, 0) sau (1, 0)).
Problema e cu atat mai mare cu cat in tot acest timp, singurul radar pornit e stricat: in loc sa arate exact locatia in care este racheta in acest moment, el a inregistrat o serie de pasi posibili pe care Bulbuka iar fi putut facut. Acesti pasi sunt urmatorii:
1 - sus sau stanga (exemplu: (0, 0) > (0, 1) sau (1, 0))
2 - jos sau dreapta (exemplu: (0, 0) > (0, 1) sau (1, 0))
3 - sus sau dreapta (exemplu: (0, 0) > (0, 1) sau (1, 0))
4 - jos sau stanga (exemplu: (0, 0) > (0, 1) sau (1, 0))
5 - sus sau stanga sau jos sau dreapta
Tu, fiind cel mai bun programator dintre cei prezenti, teai oferit sa calculezi numarul de pozitii diferite in care sar putea afla Bulbuka, pornind de la informatiile furnizate de radarul stricat.
h2. Date de intrare
Fişierul de intrare $spatiu.in$ ...
Fişierul de intrare $spatiu.in$ contine pe prima linie T, numarul de teste. In continuare, pentru fiecare test, pe o singura linie se afla numarul N, urmat de un spatiu si N numere din setul (1,2,3,4,5) reprezentand pasii din enunt. Aceste numere nu sunt separate prin spatiu.
h2. Date de ieşire
În fişierul de ieşire $spatiu.out$ ...
În fişierul de ieşire $spatiu.out$ se vor gasi T linii, iar fiecare linie va contine un numar natural reprezentand numarul de pozitii diferite calculat.
h2. Restricţii
* $... ≤ ... ≤ ...$
* T = 20
* 1 ≤ N ≤ 10^5^
h2. Exemplu
table(example). |_. spatiu.in |_. spatiu.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
3 315
2 24
| 9
4
|
h3. Explicaţie
...
In primul test:
Dupa primul pas, locatiile posibile sunt: (0, 1) sau (1, 0)
Dupa al doilea pas, locatiile posibile sunt: (1, 1), (0, 2), (0, 0) sau (1, 1)
Dupa al treilea pas, locatiile posibil sunt: (2, 1), (1, 0), (1, 2), (0, 1), (0, 1), (0, 3), (1, 0), (1, 2), (2, 1)
In al doilea test:
Dupa al doilea pas: (1, 1), (0, 2), (0, 0) sau (1, 1)
== include(page="template/taskfooter" task_id="spatiu") ==