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ț.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("fibo_gcd.in");
ofstream cout("fibo_gcd.out");

int n , x , y , cnt;

int prime_intre_ele(int a , int b)
{
    int r;
    while(b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    if(a == 1 || a == 2) return 1;
    else return 0;
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x >> y;
        if(prime_intre_ele(x , y)) cnt++;
    }
    cout << cnt;
    return 0;
}