#include <stdio.h>
int main(void)
{
	FILE *f=fopen("divmul.in","r"),*g=fopen("divmul.out","w");
	long long x,y,d,v;
	int t,i,nr;
	fscanf(f,"%d",&t);
	for (i=1;i<=t;i++)
	{
		fscanf(f,"%lld%lld",&x,&y);
		nr=0;
		if (y%x==0)
		{
		x=y/x;
		if (x%2==0)
			nr++;
		while (x%2==0) x=x/2;
		v=x;
		for (d=3;d*d<v;d=d+2)
		{
			if (x%d==0)
			{
					nr++;
				while (x%d==0)
					x=x/d;
			}
		}
		if (x>1) nr++;
			
		v=(1<<nr);
		fprintf(g,"%lld\n",v);
		}
		else 
		{
			fprintf(g,"0\n");
		}	
	}
	fclose(g);
	return 0;
}