Rezolvare PBinfo #3507

Cerința

Se consideră Șirul lui Fibonacci cunoscut prin relația de recurență: \( {F}_{1} = 1 \); \( {F}_{2} = 1 \); \( {F}_{i} = {F}_{i – 2} + {F}_{i – 1}, i ≥ 3 \).

Pentru n perechi de numere naturale x y să se afișeze numărul de perechi pentru care numerele \( {F}_{x} \) și \( {F}_{y} \) sunt prime între ele.

Date de intrare

Fișierul de intrare fibo_gcd.in conține pe prima linie numărul n, iar pe următoarele n linii n perechi de numere naturale.

Date de ieșire

Fișierul de ieșire fibo_gcd.out va conține pe prima linie numărul K, reprezentând numărul de perechi care respectă proprietatea din enunț.

Restricții și precizări

• 1 ≤ n ≤ 50.000
• 1 ≤ x, y ≤ 2.000.000.000

Exemplu:

fibo_gcd.in

5
8 7
3 4
2 1
9 6
10 5

fibo_gcd.out

3

Explicație

Primele 3 perechi satisfac condiția din enunț.