$$\sum _ {i = 1} ^ n \sum _ {j = 1} ^ m [gcd(i, j) \in prime]$$

$$\sum _ {d = 1} ^ n \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m [gcd(i, j) = d] (d \in prime)$$

$$\sum _ {d = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor} [gcd(i, j) = 1] (d \in prime)$$

$$[gcd(i, j) = 1] = \sum _ {t | gcd(i, j)} \mu(t)$$

$$\sum _ {d = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor} \sum _ {t | gcd(i, j)} \mu(t) (d \in prime)$$

$$\sum _ {d = 1} ^ n \sum _ {t = 1} ^ {\lfloor \frac n d \rfloor} \mu(t) \lfloor \frac n {dt} \rfloor \lfloor \frac m {dt} \rfloor (d \in prime)$$

$$\sum _ {T = 1} ^ n \lfloor \frac n T \rfloor \lfloor \frac m T \rfloor \sum _ {d | T} \mu(\frac T d)(d \in prime)$$

#include <bits/stdc++.h>

#define NS (10000001)
#define PS (700000)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int testcase, n, m, p[PS], cnt, mu[NS], g[NS], s[NS];

bool vis[NS];

void preWork()
{
mu[1] = 1;
for (int i = 2; i < NS; i += 1)
{
if (!vis[i]) p[++cnt] = i, mu[i] = -1;
for (int j = 1, k; j <= cnt; j += 1)
{
k = i * p[j];
if (k >= NS) break;
vis[k] = 1, mu[k] = -mu[i];
if (i % p[j] == 0) { mu[k] = 0; break; }
}
}
for (int i = 1; i <= cnt; i += 1)
for (int j = p[i]; j < NS; j += p[i])
s[j] += mu[j / p[i]];
for (int i = 1; i < NS; i += 1) s[i] += s[i - 1];
}

LL ans;

int main(int argc, char const* argv[])
{
IN(testcase), preWork();
while (testcase--)
{
IN(n), IN(m), ans = 0;
if (n > m) swap(n, m);
for (int i = 1, j; i <= n; i = j + 1)
{
j = min(n / (n / i), m / (m / i));
ans += 1ll * (n / i) * (m / i) * (s[j] - s[i - 1]);
}
printf("%lld\n", ans);
}
return 0;
}


#### Remmina

No puzzle that couldn't be solved.