#include<cstdio>
#include<cmath>
const int NMAX = 100000;// Sqrt(10 000 000)
bool ciur[NMAX + 1];
void Ciur()
{
    ciur[0] = ciur[1] = 1;
    int rad = (int)sqrt(NMAX);
    for(int i = 2; i <= rad ;i ++)
    {
    if(ciur[i] == 0)
        for(int j = i * i ; j <= NMAX ; j ++)
        {
            ciur[j] = 1;
        }
    }
}
int descompune( int n)
{
    int total = 0;
    int d = 2;
    while(d * d <= n)
    {
        if(n % d == 0){
        total ++;
        while(n % d == 0)
        n /= d;
        }
        d ++;
    }
    if(n > 1)
    total ++;
    return total;

}
int main()
{
    int Cases;
    int x , y , caut, factori_primi;
    freopen("divmul.in","r",stdin);
    freopen("divmul.out","w",stdout);
    Ciur();
    scanf("%d",&Cases);
    for(int i = 1; i <= Cases ; i ++)
    {
        scanf("%d%d", &x , &y);
        caut = y / x;
        factori_primi = descompune(y / x);
        printf("%d\n" , 1 << factori_primi);
    }
    return 0;
    }