//看看会不会爆int!
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define ROF(i, r, l) for(int i = r; i >= l; i--)
#define all(a) a.begin(), a.end()

const int maxn = 10000000;
bool nop[maxn + 10];
int pri[maxn], tot, mu[maxn + 10], T, n, m;
ll sum[maxn + 10];

void read(int &rt){
    rt=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch<='9'&&ch>='0')rt=rt*10+ch-'0',ch=getchar();
}

void pre(){
    mu[1] = 1;
    for(int i = 2, num; i <= maxn; i++){
        if(!nop[i]) pri[++tot] = i, mu[i] = -1;
        for(int j = 1; j <= tot && (num = pri[j] * i) <= maxn; j++){
            nop[num] = 1;
            if(i % pri[j]) mu[num] = -mu[i];
            else{
                mu[num] = 0;
                break;
            }
        }
    }
    for(int k = 1; k * k <= maxn; k++){
        int x = k * k;
        for(int j = x; j <= maxn; j += x)
            sum[j] += mu[j / x];
    }
    for(int i = 1; i <= maxn; i++) sum[i] += sum[i - 1];
}

int main(){
    read(T);    
    pre();
    while(T--){
        read(n), read(m);
        ll ans = 0;
        for(int i = 1, j; i <= min(n, m); i = j + 1){
            j = min(n / (n / i), m / (m / i));
            ans += (ll)(n / i) * (m / i) * (sum[j] - sum[i - 1]);
        }
        printf("%I64d\n", (ll)n * m - ans);
    }
  return 0;
}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         佛祖保佑       永无BUG
*/