#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

const int MOD = 1e9+7;
const int NMAX = 1000000;
int n;
long long v[500005];
vector<int> primi[2000005];
bool eprim[2000005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;

    while(T--)
    {
        long long n,m;
        cin>>n>>m;
        long long ans = 0;
        for(int i=1; i<=n; i++)
        {
            primi[i].clear();
        }
        for(int i=1; i<=n; i++)
        {
            vector<int> vv;
            if(i!=1 && eprim[i] == 0){
                primi[i].push_back(i);
            }
            int sz = primi[i].size();

            for(int j=0; j<(1<<sz); j++)
            {
                int cnt = 0;
                int nr = 1;
                for(int d=0; d<j; d++)
                {
                    if((j&(1<<d)))
                    {
                        cnt++;
                        nr = nr * primi[i][d];
                    }
                    //nr = nr * primi[d];

                }
                if(cnt % 2 == 1){
                    vv.push_back(-nr);
                }
                else vv.push_back(nr);

            }
            for(int j=i; j<=n; j+=i)
            {
                if(1LL*(j+1)*i >= n)
                {
                    break;
                }
                if(i!=1 && eprim[i] == 0)
                {
                    eprim[j] = 1;
                    primi[j].push_back(i);
                }
                if(i==1)
                {
                    ans += m/(j+1);
                    continue;
                }
                else
                {
                    for(auto x:vv){
                        ans += m/(j+1)/vv[x];
                    }
                }
            }


        }
        cout<<ans<<'\n';






    }



}