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 \leq 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.

Un experiment efectuat în ELHC constă în studierea unei particule de tip $G$, $1 &leq; 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 &leq; G < P < 10^9^$,
* $P$ este un număr prim,
* **Subtask 1** - $7$ puncte - $P$ &leq; $100$ ,
* **Subtask 2** - $14$ puncte - $P$ &leq; $10^4^$,
* **Subtask 3** - $53$ de puncte - $P$ &leq; $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") ==