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

constexpr int INF = 1 << 30;
constexpr int K = 50;

using lld = int64_t;

using G = vector<vector<pair<int, int>>>;

lld calc(const G &g) {
	lld ret = 0;
	for (const auto &gi : g)
		ret += ssize(gi) * (ssize(gi) - 1) / 2;
	return ret;
}

G evolve(const G &g) {
	int n = 0;
	for (const auto &gi : g)
		n += int(gi.size());
	int m = 0;
	G ret(n / 2);
	for (const auto &gi : g) {
		for (int i = 0; i < ssize(gi); ++i) {
			for (int j = i + 1; j < ssize(gi); ++j) {
				ret[gi[i].second].emplace_back(gi[j].second, m);
				ret[gi[j].second].emplace_back(gi[i].second, m);
				m += 1;
			}
		}
	}
	return ret;
}

lld solve(const G &g, int k) {
	lld ret = 0;
	vector<bool> vis(g.size());
	for (int i = 0; i < ssize(g); ++i) {
		if (vis[i])
			continue;

		int cnt = 0;
		int dc[4] = {};
		auto dfs = [&](auto self, int u) -> void {
			if (vis[u])
				return;
			cnt += 1;
			vis[u] = true;
			dc[min(3, int(g[u].size()))]++;
			for (auto [v, _] : g[u])
				self(self, v);
		};
		dfs(dfs, i);
		if (dc[3])
			return INF;
		if (dc[1]) {
			ret += max(cnt - k, 0);
		} else if (cnt != 1) {
			ret += cnt;
		}
	}
	return ret;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		int n, m, k;
		cin >> n >> m >> k;
		G g(n);
		for (int i = 0; i < m; ++i) {
			int u, v;
			cin >> u >> v;
			--u, --v;
			g[u].emplace_back(v, i);
			g[v].emplace_back(u, i);
		}

		if (k == 1) {
			cout << n << '\n';
			continue;
		}
		if (k == 2) {
			cout << min(n, m) << '\n';
			continue;
		}
		
		vector<lld> ans(K);
		ans[0] = n, ans[1] = m;
		for (int i = 2; i < K; ++i) {
			ans[i] = calc(g);
			if (i == k or ans[i] > 3 * n) {
				ans.resize(i);
				break;
			}
			g = evolve(g);
		}

		lld res = *min_element(ans.begin(), ans.end());
		if (ssize(ans) != k)
			res = min(res, solve(g, 1 + k - int(ans.size())));

		cout << res << '\n';
	}
	return 0;
}