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

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) (int((x).size()))

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef pair<int, int> pii;


int n, m, k;

struct Graph{
    int N; ll M;
    vector<vector<int>> G;
    Graph(int n, ll m) :N(n), M(m){
        G = vector<vector<int>> (n);
    }  
};

ll Calc(const Graph &now) {
    ll ans = 0;
    for(auto o : now.G) ans += 1ll * o.size() * ((int)o.size() - 1) / 2;
    return ans;
}

bool Check(const Graph &now) {
    ll ans = 0;
    for(auto o : now.G) ans += 1ll * o.size() * ((int)o.size() - 1) / 2;
    return ans <= 2 * n;
}

bool NotBigger(const Graph &now) {
    for(auto o : now.G) if(o.size() > 2) return 0;
    return 1;
}

map<pair<int, int>, int> id; 

Graph get(Graph now) {
    ll ans = Calc(now);
    Graph res = Graph(now.M, ans);
    id.clear();
    int x = 0, tot = 0;
    for(auto o : now.G) {
        vector<int> now(0);
        for(auto y : o) {
            pii edge = make_pair(min(x, y), max(x, y));
            if(!id.count(edge)) id[edge] = tot++;
            int t = id[edge];
            now.push_back(t);
        }
        for(auto a : now) for(auto b : now) if(a != b)
            res.G[a].push_back(b);
        x++;
    }
    return res;
}

void solve() {
    cin >> n >> m >> k;
    Graph st = Graph(n, m);
    for(int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;     
        x--, y--;
        st.G[x].push_back(y);
        st.G[y].push_back(x);  
    }
    int ans = n, now = 0;
    while(now <= k - 1) {
        ans = min(ans, st.N);
        if(st.M > 2 * n) break; 
        else if(Check(st) == 0) st = Graph(st.M, Calc(st));
        else if(NotBigger(st)) {
            int cnt = 0, minD = 3;
            vector<int> vis = vector<int> (st.N, 0);
            auto dfs = [&](auto self, int x) -> void {
                vis[x] = 1, cnt++, minD = min(minD, (int)st.G[x].size());
                for(auto y : st.G[x]) if(!vis[y])
                    self(self, y);
            };
            int res = 0;
            for(int i = 0; i < st.N; i++) {
                if(!vis[i]) {
                    cnt = 0, minD = 3, dfs(dfs, i);
                    if(minD == 2) res += cnt;
                    else res += max(cnt - (k - 1 - now), 0); 
                }
            }
            ans = min(ans, res);
            break;
        } else st = get(st); 
        now++;
    }    
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}
/*
4
5 5 3
1 2
1 3
1 4
2 5
4 5
5 4 3
1 2
1 3
1 4
1 5
5 4 3
1 2
2 3
3 4
4 5
5 0 3
*/

/*
1
10 7 1
1 2
3 4
5 6
7 8
8 9
9 7
10 9

*/