#include <vector>
#include <fstream>
#define N 1000001

using namespace std;

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

/*
    Ideea e sa obtinem numarul de numere MAI MICI ca A si NEPRIME cu B
    ca apoi sa il scadem din A si sa obtinem numarul de numere MAI MICI ca A si PRIME cu B

    card(A)
    folosim principiul includerii si al excluderii -
    arata cam asa

    A1- numarul de numere MAI MICI ca A si multiplii ale unui divizor prim D1 a lui B
    A2- numarul de numere MAI MICI ca A si multiplii ale unui divizor prim D2 a lui B
    A3- numarul de numere MAI MICI ca A si multiplii ale unui divizor prim D3 a lui B

    Fie x = | A1 U A2 U A3| = |A1| + |A2| + |A3| - |A1 ∩ A2| - | A2 ∩ A3 | - |A3 ∩ A1| +
    |A1 ∩ A2 ∩ A3|

    numarul cautat este    card(A) - x

    Numărul de numere mai mici ca A şi divizibile cu x va fi [A/x] (parte întreagă din A împărţit la x).
    De asemenea, dacă avem două mulţimi Ai şi Aj, i, j ≤ k, atunci  |Ai ∩ Aj| = [A / (Di * Dj].
    Acestă relaţie se extinde natural la n mulţimi.

    deci, de fapt, arata asa pentru 3 divizori

    cand spunem |Ai| asta inseamna A / Di, pentru i de la 1 la k
    cand spunem |Ai ∩ Aj| asta inseamna  A / (Di * Dj).
    etc.

*/

long long p[N],a[101],i,j,o,x,y,s,r,d,k,t,m,l;
bool v[N];

// p[] - vector de numere prime
// v[i] - vector bool care ne indica primalitatea lui i
// a[] - vector cu divizorii primi ai lui B

void ciur()
{
    for( m = N - 1, i = 2, cin >> o; i <= m ; i++)
        if(!v[i])
            for(p[++d] = i, j = i * i; j <= m ; j += i) // il bagam in vectorul de numere prime p
                v[j] = 1; // e multiplu de divizor prim
}

void rez()
{
    while(o--)
    {
        for(cin >> x >>y, l = x, k = 0, i = 1;
         i * i <= y; i++)
            if( !(y % p[i]) ) // daca se divide cu p
                for(a[++k] = p[i]; !(y % p[i]) ; y /= p[i]); //

        if(y > 1)
            a[++k] = y; // il adaugam si pe el daca mai ramane

        //aplicam chestia cu multimile
        for(t = 1 << k , i = 1; i < t; i++) // t - 1 = nr de variante de combinare posibile
            // pentru k = 3 ( adica 3 divizori primi), va trebui sa luam in considerare 7 multimi

            // i - ul ne spune cate submultimi luam o data
            // daca luam intersectie de 1 submultime, 2, 3, etc.
        {
            for(r = 1, s = j = 0; j < k; j++)
                if( (i & (1 << j)) > 0) // verificam bitii lui i
                    // i poate avea maxim 3 biti
                    // ori este activ un bit ( i este 1, 2, 4) - atunci luam o multime ( adica luam doar un divizor
                    // ori sunt activi 2 biti( i este 3, 5) ( i este  - atunci luam intersectie de doua multimi ( adica inmultim 2 divizori)
                    // ori sunt activi 3 biti( i este 7) - atunci luam intersectie de 3 multimi ( adica inmultim 3 divizori)
                    s++, r *= a[j+1]; // s ne spune cate elemente avem, r este produsul divizorilor

            l += ((s%2 == 0 ? 1 : -1) * x / r); // decidem semnul dupa s
        }

        cout << l << '\n';
    }
}

int main()
{
    ciur(); // extragem divizorii primi ai pana la 1000001
    rez();

    return 0;
}