#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC target("avx","sse2")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")

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

// https://cp-algorithms.com/algebra/linear-diophantine-equation.html
int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
    g = gcd(abs(a), abs(b), x0, y0);
    if (c % g) {
        return false;
    }

    x0 *= c / g;
    y0 *= c / g;
    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;
    return true;
}

void shift_solution(int & x, int & y, int a, int b, int cnt) {
    x += cnt * b;
    y -= cnt * a;
}

int find_all_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) {
    int x, y, g;
    if (!find_any_solution(a, b, c, x, y, g))
        return 0;
    a /= g;
    b /= g;

    int sign_a = a > 0 ? +1 : -1;
    int sign_b = b > 0 ? +1 : -1;

    shift_solution(x, y, a, b, (minx - x) / b);
    if (x < minx)
        shift_solution(x, y, a, b, sign_b);
    if (x > maxx)
        return 0;
    int lx1 = x;

    shift_solution(x, y, a, b, (maxx - x) / b);
    if (x > maxx)
        shift_solution(x, y, a, b, -sign_b);
    int rx1 = x;

    shift_solution(x, y, a, b, -(miny - y) / a);
    if (y < miny)
        shift_solution(x, y, a, b, -sign_a);
    if (y > maxy)
        return 0;
    int lx2 = x;

    shift_solution(x, y, a, b, -(maxy - y) / a);
    if (y > maxy)
        shift_solution(x, y, a, b, sign_a);
    int rx2 = x;

    if (lx2 > rx2)
        swap(lx2, rx2);
    int lx = max(lx1, lx2);
    int rx = min(rx1, rx2);

    if (lx > rx)
        return 0;
    return (rx - lx) / abs(b) + 1;
}

int solve(int n) {
//    int n;
//    cin >> n;

    int ans = 0;
    for (int x = 1; x <= n; x++) {
        for (int z = 1; z <= n; z++) {
            int mk = n * (x + z) / (x * z);
            for (int k = 1; k <= mk; k++) {
                ans += find_all_solutions(x, z, x * z * k, 1, n, 1, n);
            }
        }
    }

    return ans;
//    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen("output.txt", "w", stdout);
//    int t;
//    cin >> t;
//
//    while (t--) {
//        solve();
//    }

    for (int i = 1; i <= 1000; i++) {
        cout << solve(i) << ',';
    }
}

include<bits/stdc++.h>

using namespace std;

define int long long

define all(xs) xs.begin(), xs.end()

define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) — (x).begin())

map<int, int> mp; map<int, int> mp2; struct D {

vector<int> par;
vector<int> sz;

D(int n) {
    par.resize(n + 1);
    sz.resize(n + 1);
    for (int i = 0; i <= n; i++)
    {
        par[i] = i;
        sz[i] = 1;
        mp[i] = i;
        mp2[i] = i;
    }
    // mp.clear();
    // mp2.clear();
}

int find(int a) {
    if (a == par[a]) {
        return a;
    }
    return par[a] = find(par[a]);
}
void merge(int x, int y) {
    int p1 = find(x), p2 = find(y);
    if (sz[p1] > sz[p2]) {
        par[p2] = p1;
        sz[p1] = sz[p2] + 1;
        mp[p1] = max(mp[p1] , mp[p2]);
        // mp.erase(p2);
        mp2[p1] = min(mp2[p1] , mp2[p2]);

    }
    else {
        par[p1] = p2;
        sz[p2] = max(sz[p2], sz[p1] + 1);
        mp[p2] = max(mp[p1] , mp[p2]);
        // mp.erase(p1);
        mp2[p2] = min(mp2[p1] , mp2[p2]);


    }
}

int getmax(int i) {
    return mp[par[i]];
}
int getmin(int i) {
    return mp2[par[i]];
}

};

signed main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { mp.clear(); mp2.clear(); int n; cin >> n; D obj(n); int m; cin >> m; vector<pair<int, int>> tt; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; tt.emplace_back(u , v); obj.merge(u , v); } if (obj.find(1) == obj.find(n)) { cout << 0 << "\n"; continue ; }

int ans = (n - 1) * (n - 1) , c  = 0;
    int mn = obj.getmin(1);
    int mx = obj.getmax(1);
    int mn1 = obj.getmin(n);
    int mx2 = n;
    int d1 = abs(mn - mn1);
    ans = min(ans , d1 * d1);
    d1 = abs(mn - mx2);
    ans = min(ans , d1 * d1);
    d1 = abs(mx - mn1);
    ans = min(ans , d1 * d1);
    d1 = abs(mx - mx2);
    ans = min(ans , d1 * d1);


    // ans = min(ans , abs(n - mx));
    // ans = min(ans , abs(mn1 - mx));
    // ans = min(ans , abs(n - max(mx , mn1)));

// cout << mx

for (int i = mx + 1; i <= n; i++) {
        if (obj.find(1) != obj.find(i)  ) {
            // cout << i << " ";
            c++;
            obj.merge(1, i);
        }

        if (obj.find(1) == obj.find(n)) {
            break;
        }
    }

    // cout << c << " ";
    ans  = min(ans , c);

    c = 0;


    // ans = min(ans , abs(mx - mn1));
    // for (int i = 2; i <= n; i++) {
    //     if (obj.find(1) != obj.find(i)) {
    //         // cout << i << " ";
    //         c += (i - maxi) * (i - maxi);
    //         obj.merge(1 , i);
    //         maxi = i;
    //     }
    //     else {
    //         maxi = i;
    //     }

    //     if (obj.find(1) == obj.find(n)) {
    //         break;
    //     }
    //     mx = i;
    //     d1 = abs(mx - mn1);
    //     ans = min(ans , d1 * d1 + c);


    //     // cout << ans << " ";
    // }
    // // cout << "\n";
    // ans = min(ans , c);
    // c = 0;
    // maxi = n ;
    // mx = old;
    D obj1(n);
    for (auto [x , y] : tt) {
        obj1.merge(x , y);
    }
    c = 0;
    for (int i = mn1 -  1 ; i >= 1; i--) {
        if (obj1.find(i) != obj1.find(n)) {
            c++;
            obj1.merge(i, n);
        }
        if (obj1.find(1) == obj1.find(n)) {
            break;
        }
    }
    ans = min(ans , c);
    cout << ans << "\n";
}

}