Fişierul intrare/ieşire:	game4.in, game4.out	Sursă	Concursul Naţional de Informatică Urmaşii lui Moisil 2017
Autor	Cristian Vintur, Liana Tucar, Paul Diac	Adăugată de	Andrici Cezar •andrici_cezar
Timp execuţie pe test	2 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Game4

Alice si Bob joacă un joc matematic în care cei doi mută alternativ. Iniţial, ei pornesc jocul cu un şir de N numere naturale nenule a ₁ a ₂ ... a _N . O mutare constă în alegerea unui număr de forma p _k , unde p este un număr prim iar k un număr natural nenul, urmată de împărţirea prin p _k a tuturor numerelor a _i care se divid cu această valoare (trebuie să existe în şirul curent cel puţin o valoare a _i care va fi modificată în această etapă). Alice face mereu prima mutare. Câştigă cel care realizează ultima mutare, iar cel care nu mai poate muta, pierde (toate valorile a _i au devenit 1). La fiecare mutare, dacă jucătorul curent are strategie de câştig, va juca aplicând acestă strategie. În caz contrar, jucătorul este nevoit să facă o mutare posibilă.

Cerinţă

1. Determinaţi câştigătorul jocului.
2. Determinaţi numărul V de variante distincte de a face prima mutare, pentru jucătorul care câştigă jocul. De exemplu, presupunând că Alice câştigă, V = numărul de valori p _k distincte, pe care le poate alege Alice la prima ei mutare, astfel încât să fie sigură că va câştiga jocul în final. Presupunând că Bob va câştiga jocul, V = numărul de valori p _k distincte, dintre care poate alege Bob la prima lui mutare, astfel încât el să câştige în final (nu uitaţi că Alice începe jocul). Dacă Bob poate alege aceeaşi valoare p _k pentru două variante diferite ale mutării iniţiale a lui Alice, valoare care l-ar duce la câştig, se va număra o singură dată această valoare.

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 ₁ a ₂ ... a _N separate prin câte un spaţiu. Pentru toate testele din acelaşi fişier se rezolvă aceeaşi cerinţă C.

Date de ieşire

Fişierul de ieşire game4.out va conţine T linii, pe linia i va fi răspunsul pentru testul al i-lea.
Dacă C = 1, se afişează pentru fiecare joc, numele câştigătorului „Alice” sau „Bob”.
Dacă C = 2, se afişează pentru fiecare joc, numărul V de mutări distincte dintre care câştigătorul ar putea alege prima sa mutare, conform precizărilor de la punctul 2.

Restricţii

• 2 < T < 10
• 1 < N < 100.000
• 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

Exemplu

Explicaţie

...

Explicaţie

Sunt 4 teste de rezolvat pe cerinţa 2 (vezi explicaţia de mai sus).
În primul joc, N=2 şi a ₁ = 7, a ₂ = 25 şi câştigă Alice, care poate alege iniţial doar varianta p^k = 5¹ 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¹ , p^k = 3¹ sau p^k = 7¹. 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ă.

Cum se trimit solutii?