h2. Date de intrare

Fişierul de intrare $game4.in$ conţine $T$ teste. Pe prima linie se află numerele naturale $T$ şi $C$, numărul de teste, respectiv cerinţa ($1$ sau $2$). Următoarele $T$ linii conţin câte un joc dat prin $N$ şi numerele $a{~1~} a{~2~} ... a{~N~}$ separate prin câte un spaţiu. Pentru toate testele din acelaşi fişier se rezolvă aceeaşi cerinţă $C$.

Fişierul de intrare $game4.in$ conţine $T$ teste. Pe prima linie se află numerele naturale $T$ şi $C$, numărul de teste, respectiv cerinţa ({$1$} sau $2$). Următoarele $T$ linii conţin câte un joc dat prin $N$ şi numerele $a{~1~} a{~2~} ... a{~N~}$ separate prin câte un spaţiu. Pentru toate testele din acelaşi fişier se rezolvă aceeaşi cerinţă $C$.

h2. Date de ieşire

* $2 < T < 10$
* $1 < N < 100.000$

* $1 < a ~i~ < 1.000.000,1 < i < N$

* $1 < a{~i~} < 1.000.000,1 < i < N$

* $Pentru teste în valoare de 40 puncte, C = 1.$
* $Pentru teste în valoare de 60 puncte, C = 2. Pentru o parte dintre acestea, în valoare de 20 puncte, Alice câştigă întotdeauna.$

* $Pentru teste în valoare de 30 puncte, a i < 20, 1 < i < N$

* $Pentru teste în valoare de 30 puncte, a{~i~} < 20, 1 < i < N$

h2. Exemplu

h4. Explicaţie

...

Sunt $4$ teste de rezolvat pe cerinţa $1$.
În primul joc, $N=2$ şi $a{~1~} = 7$, $a{~2~} = 25$ şi câştigă Alice.
Ea poate alege iniţial $p^k^ = 5^1^$, $p^k^ = 5^2^$ sau $p^k^ = 7^1^$ . Pot avea loc variantele:
 
* $p^k^ = 5^1^$, împarte la $5^1^$ valorile şi obţine $a{~1~} = 7$ şi $a{~2~} = 5$. Dacă acum Bob alege $7$ se obţine $a{~1~} = 1$ şi $a{~2~} = 5$. Alice va alege $5$, se va obţine $a{~1~} = 1$ şi $a{~2~} = 1$ şi ea va câştiga. Analog s-ar fi întâmplat dacă Bob ar fi ales $5$ în loc de $7$.
* Cazurile $p^k^ = 5^2^$ sau $p^k^ = 7^1^$ pentru prima mutare a lui Alice îi vor permite lui Bob să aleagă fie $7$ fie $5^2^$ şi să câştige. În concluzie, Alice câştigă numai dacă alege $p^k^ = 5^1^$.
 
În al doilea joc, $N=2$ şi $a{~1~} = 10$, $a{~2~} = 21$ şi câştigă Bob.
Alice poate alege iniţial $p^k^ = 2^1^$, $p^k^ = 5^1^$, $p^k^ = 3^1^$ şi $p^k^ = 7^1^$. Pentru fiecare alegere a lui Alice, Bob poate alege oricare dintre celelalte trei variante rămase. În următoarele două mutări, o alegere va fi a lui Alice şi ultima valoare va fi aleasă de Bob, care va câştiga.

table(example). |_. game4.in |_. game4.out |
| 4 2

Sunt $4$ teste de rezolvat pe cerinţa $2$ (vezi explicaţia de mai sus).
În primul joc, $N=2$ şi $a{~1~} = 7$, $a{~2~} = 25$ şi câştigă Alice, care poate alege iniţial doar varianta $p^k^ = 5^1^$ care îi permite să câştige. Aşadar, sunt $V = 1$ variante distincte.

În al doilea joc, dacă Alice alege $p^k = 2^1$ , Bob poate alege iniţial $p^k^ = 5^1^$ , $p^k^ = 3^1^$ sau $p^k^ = 7^1^$. Similar, dacă Alice alege oricare dintre $p^k^ = 5^1^$, $p^k^ = 3^1^$ sau $p^k^ = 7^1^$ , Bob va putea alege prima mutare dintre celelalte $3$ variante rămase. În concluzie, numărul de valori distincte pe care Bob le poate alege iniţial este $V = 4$.

În al doilea joc, dacă Alice alege $p^k^ = 2^1^$ , Bob poate alege iniţial $p^k^ = 5^1^$ , $p^k^ = 3^1^$ sau $p^k^ = 7^1^$. Similar, dacă Alice alege oricare dintre $p^k^ = 5^1^$, $p^k^ = 3^1^$ sau $p^k^ = 7^1^$ , Bob va putea alege prima mutare dintre celelalte $3$ variante rămase. În concluzie, numărul de valori distincte pe care Bob le poate alege iniţial este $V = 4$.

Observăm că Bob poate alege ca primă mutare, $p^k^ = 3^1^$ în toate cele trei cazuri când Alice a ales iniţial $p^k^ = 2^1^$ sau $p^k^ = 5^1^$ sau $p^k^ = 7^1^$, dar această mutare se numără o singură dată.
== include(page="template/taskfooter" task_id="game4") ==