== include(page="template/taskheader" task_id="elhc") ==
Poveste şi cerinţă...
După şase ani de lucru, Charles a terminat de curăţat instalaţiile pentru producerea negrului de fum din Copşa Mică. Pentru a se ţine departe de mesele de Blackjack, el s-a angajat la CERN, unde va lucra la noul accelerator de particule numit Even Larger Hadron Collider (ELHC).
ELHC are forma unui tunel circular cu o circumferinţă de $P$ kilometri, $P$ fiind un număr prim. De-a lungul tunelului sunt plasaţi $P$ senzori numerotaţi de la $0$ la $P-1$, distanţa dintre doi senzori consecutivi fiind de exact $1$ kilometru.
Un experiment efectuat în ELHC constă în studierea unei particule de tip $G$, $1 ≤ G < P$. Dacă această particulă este ridicată la nivelul de energie $k$ şi este lansată din dreptul senzorului $0$ în direcţia senzorului $1$, ea va parcurge exact $G^k$ kilometri prin tunel şi apoi se va dezintegra, declanşând în acel moment senzorul $s$ în dreptul căruia are loc dezintegrarea particulei.
Se consideră că experimentul are date complete dacă, lansând $P-1$ particule de tip $G$ ridicate la toate nivelurile de energie $k$ de la $1$ la $P-1$, este posibil să declanşăm toţi senzorii $s$ numerotaţi cu valori între $1$ şi $P-1$, adică toţi senzorii din tunel mai puţin senzorul $0$.
Dându-se $T$ perechi de numere $G$ şi $P$, determinaţi dacă experimentul pentru studierea particulei de tip $G$ într-un tunel de circumferinţă $P$ produce date complete.
h2. Date de intrare
Fişierul de intrare $elhc.in$ ...
Fişierul de intrare $elhc.in$ conţine pe prima linie un număr $T$, reprezentând numărul de experimente care vor fi efectuate. Pe fiecare din următoarele $T$ linii se află câte două numere $G$ şi $P$ separate printr-un spaţiu, reprezentând efectuarea unui experiment cu o particulă de tip $G$ într-un tunel de circumferinţă $P$.
h2. Date de ieşire
În fişierul de ieşire $elhc.out$ ...
În fişierul de ieşire $elhc.out$ se va afla o singură linie cu $T$ biţi scrişi unul după altul, adică fără spaţii între ei. Al $i$-ulea bit este $1$ dacă pentru cel de-al $i$-lea experiment putem obţine date complete, şi $0$ în caz contrar.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10^3^$,
* $1 ≤ G < P < 10^9^$,
* $P$ este un număr prim,
* **Subtask 1** - $7$ puncte - $P$ ≤ $100$ ,
* **Subtask 2** - $14$ puncte - $P$ ≤ $10^4^$,
* **Subtask 3** - $53$ de puncte - $P$ ≤ $10^6^$,
* **Subtask 4** - $26$ de puncte - nu există restricţii suplimentare.
h2. Exemplu
table(example). |_. elhc.in |_. elhc.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
2 3
3 5
2 7
3 7
3 11
5 11
| 110100
|
h3. Explicaţie
...
Fişierul de intrare conţine $T=6$ experimente.
A doua particulă are tipul $3$ şi va fi lansată printr-un tunel de circumferinţă $5$, cu $5$ senzori numerotaţi de la $0$ la $4$. Ridicată la nivelurile de energie $1$, $2$, $3$, respectiv $4$, şi lansată de fiecare dată din dreptul senzorului $0$, particula va călători $3$, $9$, $27$, respectiv $81$ de kilometri şi va declanşa senzorii $3$, $4$, $2$, respectiv $1$. Aceştia sunt toţi senzorii pe care trebuie să-i declanşăm, prin urmare experimentul produce date valide, deci al doilea bit din şirul afişat este $1$.
A treia particulă are tipul $2$ şi va fi lansată printr-un tunel de circumferinţă $7$. Ridicată la nivelurile de energie $1$, $2$, $3$, $4$, $5$, respectiv $6$, şi lansată de fiecare dată din dreptul senzorului $0$, particula va declanşa senzorii $2$, $4$, $1$, $2$, $4$, respectiv $1$. Deoarece nu declanşăm senzorii $3$, $5$ şi $6$, experimentul nu are date complete, deci al treilea bit din şirul afişat este $0$.
== include(page="template/taskfooter" task_id="elhc") ==
