Author: Kamonasish Roy
Tester : Emon Thakur, Abu Sufian Rafi.
Editorial:

• Key observations
  Let d = |i − j|.
  Because gcd(i, j) = d, the difference d must divide both i and j, so

 i = k·d, j = (k + 1)·d for some integer k ≥ 1.

(The order can be swapped, but we enforce i ≤ j.)
Conversely, for any d and any k with (k + 1)·d ≤ N the pair
(k·d, (k + 1)·d) satisfies gcd = d, because k and k + 1 are always coprime.

Therefore, for a fixed difference d the number of valid pairs equals

 ⌊N / d⌋ − 1.    (the largest possible k is ⌊N/d⌋ − 1)

Total pairs = Σ₍d = 1…N₎ (⌊N/d⌋ − 1).

• Efficient counting with a sieve‑style loop
  Directly summing the formula per query costs O(N) which is too slow.
  Instead we pre‑count for every m ≤ 10⁶ how many pairs end at position m.

Idea:
If j = m is fixed, all harmonious i are j − d where d divides both numbers,
so i is any proper divisor of m (excluding m itself).
Hence the number of harmonious pairs that end at j is (number of divisors of j) − 1.

We can compute “divisor count minus one” for every j in O(N log N) by
the classic harmonic‑series sieve:

 for i from 1 to N
for j = 2·i, 3·i, … ≤ N
dp[j] ++   // i is a proper divisor of j

Afterwards dp[j] holds the new pairs whose larger index equals j.
A prefix sum over dp gives ans[n] = Σ₍j ≤ n₎ dp[j],
so every query is answered in O(1).

Code (C++):

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 1;
int dp[MAXN];

void precompute() {
    for (int i = 1; i < MAXN; ++i)
        for (int j = i + i; j < MAXN; j += i)
            dp[j]++;                 // i is a proper divisor of j
    for (int i = 1; i < MAXN; ++i)
        dp[i] += dp[i - 1];          // prefix sum
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();

    int T;            // number of test cases
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        cout << dp[N] << '\n';
    }
    return 0;
}