#include <bits/stdc++.h>
namespace Qiaoqia {
void solve() {
	std::cin >> n >> rt;
	for (int i = 1; i <= n; i++) g[i].clear();
	for (int i = 1, x, y; i < n; i++) {
		std::cin >> x >> y;
		g[x].push_back(y), g[y].push_back(x);
	}
	dfs(rt, 0);
	for (int i = 1; i <= n; i++) p[i] = i;
	int ans = 0;
	do {
		if (p[1] != rt) continue;
		for (int i = 1; i <= n; i++) cnt[i] = 0;
		int u = p[1];
		int an = 0;
		for (int i = 1; i <= n; i++) {
			if (i != 1)
			if ((fa[p[i + 1]] != p[i] && p[i + 1] != fa[p[i]]) ||
				(fa[p[i + 1]] == fa[p[i]] && cnt[p[i]] != sz[p[i]]) {
				an = 1;
				break;
			}	
			
		}
	} while (std::next_permutation(p + 1, p + 1 + n));
	std::cout << ans << '\n';
}

void main() {
	int T;
	std::cin >> T;
	while (T--) solve();
}
}
void _() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); }
int main() { void IO(); IO(); _(); Qiaoqia::main(); }

// It's over.
// whk, goodday.
