Pracsiu Dan (dnprx) 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 Gk 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.
Cerința
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.
Date de intrare
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.
Date de ieșire
Î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.
Restricții și precizări
1 ≤ T ≤ 1 0001 ≤ G < P < 1 000 000 000Peste un număr prim
Exemplu:
elhc.in
6 2 3 3 5 2 7 3 7 3 11 5 11
elhc.out
110100
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.