Soluții trimise

Cătălin este cel mai important general din armata țării sale, care are N membri (soldați și ofițeri), numerotați de la 1 la N (Cătălin are numărul 1). Un ofițer este un soldat care are în subordinea sa alți soldaţi. Conform ierarhiei militare, Cătălin și toți ceilalți ofițeri primesc inițial 3 subalterni (soldații cu numerele 2, 3 şi 4). Fiecare dintre cei trei, primește la rândul lui alți 3 subalterni, după următoarea regulă: ofițerul cu numărul x primește subalternii 3 * x – 1, 3 * x, 3 * x + 1 (dacă aceștia există în armată).

S-a descoperit că în această armată există trădători. Mai exact, toți cei numerotați cu numere prime sunt dovediți trădători, iar Cătălin știe bine asta, asa că ia măsuri radicale: decide să îi elimine pe rând pe toți acești misei, începând chiar cu subalternul său cu numărul 2. Dacă ofițerul cu numărul X este eliminat, toți subalternii săi devin subalternii comandantului său. Eliminându-l pe 2, subalternii acestuia devin subalternii comandantului lui 2, adică ai lui Cătălin. După trista eliminare a lui 2, Cătălin trece mai departe și elimină pe rând pe cei cu numerele 3, 5, 7, 11, 13 … Subalternii lui 3, 5, 7 devin subalternii lui 1, cei ai lui 11 devin ai lui 4 și tot așa.

După măcel, Cătălin trebuie să răspundă la Q întrebări ale împăratului care dorește să afle câți subalterni are un membru x al armatei sale. Dacă x a fost eliminat, Cătălin va transmite pentru acesta răspunsul -1.