B with DSU+LCA

#include <bits/stdc++.h>
// tiom4eg's precompiler options
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
// IO settings
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
// Quick types
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define mi vector <vector <int> >
// Quick functions
#define endl "\n"
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
#define fint(n) int n; cin >> n
#define fstr(s) string s; cin >> s
#define farr(a, n) int a[n]; for (int pog = 0; pog < n; ++pog) cin >> a[pog]
#define min(a, b) ((a < b) ? (a) : (b))
#define max(a, b) ((a > b) ? (a) : (b))
// Quick fors
#define FOR1(s, n) for (int i = s; i < n; ++i)
#define FOR2(s, n) for (int j = s; j < n; ++j)
#define FOR3(s, n) for (int k = s; k < n; ++k)
#define RFOR(n, s) for (int l = n; l >= s; --l)
// Pragmas
#pragma GCC optimize("Ofast") // let the chaos begin!
#pragma GCC optimize ("unroll-loops")
#pragma target("avx,fma")
#pragma comment(linker, "/stack:200000000")
#pragma target("tune=native")
// PBDS
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>
#define ook order_of_key
#define fbo find_by_order
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
using namespace std;
using namespace __gnu_pbds;
mt19937 rng(std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count());

const int MAX = 100005, LOG = 18, INF = 2e9;

int p[MAX], h[MAX];

// DSU with ranks
int get(int u) {
    if (p[u] == -1) return u;
    return p[u] = get(p[u]);
}

bool check(int v, int u) {
    return get(v) == get(u);
}

void unite(int v, int u) {
    v = get(v), u = get(u);
    if (h[v] > h[u]) swap(v, u);
    p[v] = u;
    if (h[v] == h[u]) h[u]++;
}

// LCA
int l = 1, timer = 0;
vector <pii> g[MAX];
int tin[MAX], tout[MAX];
pii up[MAX][LOG];

void dfs(int v, int p = 1, int c = INF) {
    tin[v] = timer++, up[v][0] = {p, c};
    FOR1(1, l + 1) up[v][i] = {up[up[v][i - 1].F][i - 1].F, max(up[v][i - 1].S, up[up[v][i - 1].F][i - 1].S)};
    for (auto& u : g[v]) if (u.F != p) dfs(u.F, v, u.S);
    tout[v] = timer++;
}

bool upper(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }

int lca(int a, int b) {
    int ans = 0;
    for (int i = l; i >= 0; i--) if (!upper(up[a][i].F, b)) ans = max(ans, up[a][i].S), a = up[a][i].F;
    if (!upper(a, b)) ans = max(ans, up[a][0].S);
    for (int i = l; i >= 0; i--) if (!upper(up[b][i].F, a)) ans = max(ans, up[b][i].S), b = up[b][i].F;
    if (!upper(b, a)) ans = max(ans, up[b][0].S);
    return ans;
}

int main() {
    fastIO;
    int n, m, q; cin >> n >> m >> q;
    while ((1 << l) <= n) ++l;
    FOR1(1, n + 1) p[i] = -1, h[i] = 1;
    // Simulate
    FOR1(1, m + 1) {
        int sp = m + 1 - i;
        for (int j = 2; j * sp <= n; ++j) {
            if (!check(sp, j * sp)) {
                unite(sp, j * sp);
                g[sp].pb({j * sp, i});
                g[j * sp].pb({sp, i});
            }
        }
    }
    // Now to answer queries just find maximum on path from A to B
    dfs(1);
    FOR1(0, q) {
        int a, b; cin >> a >> b;
        if (a == b) cout << 0 << endl;
        else cout << lca(a, b) << endl;
    }
}