# include <fstream>
# include <bitset>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

bool prim(int n) {
    if (n < 2)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    for (int d=3; d*d<=n; d+=2)
        if (n%d == 0)
            return false;
    return true;
}

const int MAX = 200; // 1e12 are 168 de divizori
int D[MAX];

int pinex(int a, int b) {
    bitset<MAX> v;
    long long   finAns = 0, // rezultatul final
                prodDiv = 0; // produsul divizorilor
    int tmpNr = 0, // numarul de 1 din submultime
        k = 0,
        i = 0;

    for (int d=1; d*d<=b; d++) {
        if (b % d == 0) {
            if (prim(d))
                D[++k] = d;

            if ((b/d != d) && prim(b/d))
                D[++k] = b/d;
        }
    }

    printf ("Divizorii primi ai lui %d:\t", b);
    for (int j=1; j<=k; j++)
        printf ("%d ", D[j]);
    printf ("\nSuma: ");

    while (v[0] == 0) {
        i = k;
        while (v[i] == 1) {
            v[i] = 0;
            i--;
        }
        v[i] = 1;

        tmpNr = 0;
        prodDiv = 1;
        for (i=1; i<=k; i++)
            if (v[i] == 1) {
                tmpNr++;
                prodDiv *= D[i];
            }

        if (tmpNr > 0) {
            if (prodDiv != 0)
                prodDiv = a/prodDiv;

            if ((tmpNr - 1) % 2 == 1)
                prodDiv *= (-1);

            printf("+ (%d)", prodDiv);
            finAns += prodDiv;
        }
    }
    printf("\n");

    return finAns;
}

int T, a, b;
int main() {
    for (fin >> T; T; --T) {
        fin >> a >> b;
        fout << a - pinex(a, b) << "\n";
    }
    return 0;
}