loterie

Loterie

== include(page="template/taskheader" task_id="loterie") ==

Poveste şi cerinţă...

Ramas fara mijloace pentru a-si finanta cariera de jucator profesionist de FIFA, RMN a ales sa joace la Loteria Primelor. Acesta va participa la $q$ extrageri. La fiecare dintre ele i se va oferi un interval de forma $[a,b]$ din care RMN trebuie sa aleaga $2$ numere naturale distincte. In cazul in care cele $2$ numere alese sunt prime intre ele, el castiga extragerea si o suma considerabila.
 
Eroul nostru considera ca alegerea la intamplare a celor $2$ numere nu este destul de profitabila, asa ca va roaga sa calculati numarul de perechi castigatoare pentru fiecare extragere.
 

h2. Date de intrare

Fişierul de intrare $loterie.in$ ...

Fişierul de intrare $loterie.in$ va contine pe prima linie un numar natural $q$, numarul de extrageri. Pe urmatoarele $q$ linii se vor afla cate $2$ numere naturale $a$ si $b$ ce reprezinta capetele intervalului de la extragerea respectiva.

h2. Date de ieşire

În fişierul de ieşire $loterie.out$ ...

În fişierul de ieşire $loterie.out$ se vor afla q numere, numarul de pe linia i reprezentand numarul de alegeri castigatoare pentru extragerea i.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $q ≤ 100.000$
* $a ≤ 100$, pentru orice extragere
* $b ≤ 50.000$, pentru orice extragere
* Perechea $(a,b)$ nu este diferita de perechea $(b,a)$
* Pentru $20%$ din teste $q ≤ 1000$ si $a ≤ b ≤ 100$

h2. Exemplu
table(example). |_. loterie.in |_. loterie.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
  2 5
  1 1
| 5
  0

|
h3. Explicaţie

...

In primul caz, perechile castigatoare sunt $(2,3),(2,5),(3,4),(3,5),(4,5)$
 
In cel de-al doilea caz nu exista nicio pereche castigatoare.

== include(page="template/taskfooter" task_id="loterie") ==