//0124
#include <cstdio>
#include <list>
#define li list<int>::iterator

using namespace std;

int main() {
    FILE* fi = fopen("divmul.in", "rt");
    FILE* fo = fopen("divmul.out", "wt");

    bool p[10005];
    list<int> prime;
    for (int i = 1; i <= 10000; i++) {
        p[i] = true;
    }
    for (int i = 2; i <= 10000; i++) {
        if (p[i]) {
            prime.push_back(i);
            for (int j = i * i; j <= 10000; j += i) {
                p[j] = false;
            }
        }
    }

    int totaltest;
    fscanf(fi, "%d", &totaltest);

    for (int test = 1; test <= totaltest; test++) {
        long x, y;
        fscanf(fi, "%ld%ld", &x, &y);
        if (x > y) {
            fprintf(fo,"0\n");
            continue;
        }
        if (y % x != 0) {
            fprintf(fo, "0\n");
            continue;
        }
        y /= x;
        int put = 0;
        for (li it = prime.begin(); it != prime.end(); it++) {
            int aux = *it;
            if (y % aux == 0) {
                put++;
                while (y % aux == 0)
                    y /= aux;
            }
            if (aux * aux > y) {
                break;
            }
        }
        if (y != 1) {
            put++;
        }
        long ans = 1;
        for (int i = 1; i <= put; i++) {
            ans *= 2;
        }
        fprintf(fo, "%ld", ans);
    }

    return 0;
}