#include
using namespace std;
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
const int maxn = 10000009;
int tp, pn[maxn], mu[maxn], h[maxn]; dint sh[maxn]; bool pr[maxn];
void pre() { memset(pr, 0, sizeof(pr)); tp = 0; mu[1] = 1; sh[0] = sh[1] = 0; for (int i = 2; i < maxn; ++ i) { if (!pr[i]) { pn[tp ++] = i; mu[i] = -1; h[i] = 1; } for (int j = 0, v; j < tp && i * pn[j] < maxn; ++ j) { pr[v = i * pn[j]] = 1; if (i % pn[j] == 0) { mu[v] = 0; h[v] = mu[i]; break; } else { mu[v] = -mu[i]; h[v] = mu[i] - h[i]; } } sh[i] = sh[i - 1] + h[i]; } }
int main() { pre(); int t; scanf("%d", &t); while (t –) { int a, b; dint s(0); scanf("%d%d", &a, &b); if (a > b) swap(a, b); for (int i = 1, j; i <= a; i = j + 1) { j = min(a / (a / i), b / (b / i)); s = s + (sh[j] - sh[i - 1]) * (a / i) * (b / i); } printf(lld “\n”, s); } }