#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#define in(x) x=read()
#define qr read()
#define int ll
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO
{
    #define BUF_SIZE 100000
    bool IOerror=0;
    inline char nc()
	{
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline ll read()
	{
        bool sign=0; char ch=nc();ll x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return 0;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
        return x;
    }
    #undef BUF_SIZE
};
using namespace fastIO;
int pos[100][100],vv[1000010],a[100],b[100],res[100],MX[100][100],ans[100],f[100][100];
vector<pii>lis,V[100];
unordered_map<int,int>w;
inline int gcd(int x,int y){if(x%y==0)return y;return f[x%y][y];}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int T=qr,mx=0;
	ans[0]=1;
	for(int i=1;i<=60;i++)
	{
		for(int j=1;j<=60;j++)f[i][j]=__gcd(i,j);
	}
	for(int i=1;i<=T;i++)
	{
		in(a[i]),in(b[i]);
		mx=max(mx,b[i]);
		V[b[i]].push_back(mp(a[i],i));
		for(int j=1;j<=b[i];j++)
		{
			pos[i][j]=j*a[i]/b[i];
			MX[b[i]][j]=max(MX[b[i]][j],pos[i][j]);
		}
	}
	for(int k=1;k<=mx;k++)
	{
		if(!V[k].size())continue;
		// int n=1e12,k=59;
		for(int i=1;i<=k;i++)
		{
			// pos[i]=i*n/k;
			vv[i]=i/__gcd(i,k);
		}
		lis.clear();
		int sum=0;
		for(int i=k-1;i>=1;i--)
		{
			if(k%i==0)
			{
				for(auto id:V[k])res[id.se]+=pos[id.se][i];
				break;
			}
			int v=vv[i];
			w.clear();
			for(auto j:lis)
			{
				if(j.fi<=MX[k][i])w[j.fi]+=j.se;
				int nxt=j.fi*v/gcd(j.fi,v); 
				if(nxt<=MX[k][i])w[nxt]-=j.se;
			}
			sum+=lis.size();
			w[v]++;
			// cout<<pos[i]<<"~"<<pos[i-1]<<":\n";
			lis.clear();
			for(auto j:w)
			{
				// cout<<j.fi<<','<<j.se<<'\n';
				if(j.se)lis.push_back(mp(j.fi,j.se));
			}
			sum+=w.size();
			for(auto id:V[k])
			{
				for(auto j:lis)
				{
					res[id.se]+=(pos[id.se][i]/j.fi)*j.se-(pos[id.se][i-1]/j.fi)*j.se;
				}
			}
			sum+=lis.size();
			// cout<<i<<":"<<sum<<'\n';
		}
		// cout<<res<<'\n';
	}
	for(int i=1;i<=T;i++)cout<<res[i]<<'\n';
	return 0;
}