#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 50;
const int K = 5;

int n, m, k;

struct answer_t {
	int64_t a, b;
	answer_t() : a(0), b(1) {

	}
	answer_t(int64_t a, int64_t b) : a(a), b(b) {
	}
	answer_t operator+(const answer_t &rhs) const {
		if (a == rhs.a)
			return answer_t(a, b + rhs.b);
		if (a > rhs.a)
			return *this;
		return rhs;
	}
	answer_t& operator +=(const answer_t &rhs) {
		return *this = *this + rhs; 
	}
};

int d[N];
answer_t f[N][K];
vector<int> G[N];

answer_t s1() {
	answer_t res;
	for (int i = 1; i <= n; ++i) {
		res += answer_t(d[i], 1);
	}
	return res;
}

answer_t s2() {
	answer_t res;
	for (int i = 1; i <= n; ++i) {
		for (int j : G[i]) {
			if (i <= j) {
				res += answer_t(d[i] + d[j] - 2, 1);
			}
		}
	}
	return res;
}

answer_t gao(answer_t c0, answer_t c1) {
	assert(c0.b >= 1);
	if (c0.b == 1) {
		return answer_t(c0.a + c1.a, c0.b * c1.b);
	}
	return answer_t(c0.a * 2, c0.b * (c0.b - 1) / 2);
};

answer_t s3() {
	// d_u + d_v + 2d_x - 6
	answer_t res;
	for (int x = 1; x <= n; ++x)
		if (d[x] >= 2) {
			if (f[x][0].b == 1) {
				int64_t val = f[x][0].a + f[x][1].a + 2 * d[x] - 6;
				int64_t ways = f[x][0].b * f[x][1].b;
				res += answer_t(val, ways);
			}
			else {
				int64_t val = 2 * f[x][0].a + 2 * d[x] - 6;
				int64_t ways = f[x][0].b * (f[x][0].b - 1) / 2;
				res += answer_t(val, ways);
			}
		}
	return res;
}

answer_t s4() {
	answer_t res;
	for (int x = 1; x <= n; ++x) {
		for (int y : G[x]) {
			if (x <= y) {
				vector<answer_t> gx, gy;
				auto gogo = [&](int x, int y, auto &v) {
					for (int _ = 0; _ < K; ++_) {
						answer_t cur = f[x][_];
						if (f[x][_].a == d[y]) {
							--cur.b;
						}
						if (cur.b <= 0) continue;
						v.push_back(cur);
					}
				};
				auto gogogo = [&](int x, int y, auto &v) {
					if (d[x] < 3) return answer_t(-1, 0);
					assert(v.size() >= 2);
					answer_t z = gao(v[0], v[1]);
					z.a += 4 * d[x] + 2 * d[y] - 14;
					return z;
				};
				gogo(x, y, gx), gogo(y, x, gy);
				res += gogogo(x, y, gx);
				res += gogogo(y, x, gy);
				if (d[x] >= 2 && d[y] >= 2) {
					int64_t val = gx[0].a + gy[0].a + 3 * d[x] + 3 * d[y] - 14;
					int64_t ways = gx[0].b * gy[0].b;
					res += answer_t(val, ways);
				}
			}
		}
	}
	return res;
}

void init_f() {
	for (int x = 1; x <= n; ++x) {
		for (int y : G[x]) {
			answer_t z(d[y], 1);
			for (int i = 0; i < K; ++i) {
				if (z.a == f[x][i].a) {
					f[x][i].b += z.b;
					break;
				}
				else if (z.a > f[x][i].a) {
					swap(z, f[x][i]);
				}
			}
		}
	}
}

vector<vector<pair<int, int>>> linegraph(vector<vector<pair<int, int>>> G) {
	int n = G.size();
	int tot = 0;
	int m = 0;
	for (int x = 1; x < n; ++x)
		m += G[x].size();
	assert(m % 2 == 0);
	m /= 2;
	vector<vector<pair<int, int>>> H(m + 1);
	int etot = 0;
	for (int x = 1; x < n; ++x) {
		for (auto [y, ye_id] : G[x]) {
			for (auto [z, ze_id] : G[x]) {
				if (y == z) break;
				++etot;
				H[ye_id].emplace_back(ze_id, etot);
				H[ze_id].emplace_back(ye_id, etot);
			}
		}
	}	
	return H;
}

answer_t solve2() {
	vector<vector<pair<int, int>>> GG(n + 1);
	int etot = 0;
	for (int x = 1; x <= n; ++x) {
		for (int y : G[x]) if (x < y) {
			++etot;
			GG[x].emplace_back(y, etot);
			GG[y].emplace_back(x, etot);
		}
	}
	for (int i = 0; i < k - 1; ++i) {
		GG = linegraph(GG);
	}
	int atot = 0;
	static int vis[N];
	for (int i = 0; i < N; ++i)
		vis[i] = 0;
	int cs = 0;
	for (int x = 1; x < GG.size(); ++x) {
		++cs;
		for (auto [y, _1] : GG[x]) {
			vis[y] = cs;
		}
		for (auto [y, _1] : GG[x])
			for (auto [z, _2] : GG[y]) {
				if (vis[z] == cs) {
					++atot;
				}
			}
	}
	assert(atot % 6 == 0);
	atot /= 6;
	if (atot == 0) return answer_t();
	return answer_t(3, atot);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m >> k;
		for (int i = 0; i < m; ++i) {
			int u, v;
			cin >> u >> v;
			G[u].push_back(v);
			G[v].push_back(u);
			++d[u], ++d[v];
		}
		init_f();
	
		answer_t ans;
		if (k == 1) ans = s1();
		else if (k == 2) ans = s2();
		else if (k == 3) ans = s3();
		else if (k == 4) ans = s4();
		if (ans.a <= 3)
			ans += solve2();
		if (ans.a == 0) ans.b = 1;
		if (ans.a == 1) ans.b /= 2;
		cout << ans.a << " " << ans.b % 1'000'000'007 << '\n';
		for (int i = 0; i <= n; ++i) {
			G[i].clear();
			d[i] = 0;
			for (int j = 0; j < K; ++j) {
				f[i][j] = answer_t();
			}
		}
	}
}