#include <bits/stdc++.h>
using namespace std;
int main(){
	int a, b;
	scanf("%d%d", &a, &b);
	printf("%d\n", a >= b);
}

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

bool isp(int x){
	if (x < 2)return false;
	for (int i = 2; i * i <= x; ++i)if (x % i == 0)return false;
	return true;
}

int main(){
	int x;
	scanf("%d", &x);
	if (isp(x - 2))printf("%d %d\n", 2, x - 2);
	else printf("-1\n");
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 1000000;
int dpfr[2][N + 1], dp[N + 1], n, gr[N + 1];
vector<int> tr[N + 1];

vector<int> cn;
int getcn(int v = 1, int p = 0){
	bool ok = true;
	int s = 1;
	f(i, 0, tr[v].size()){
		int u = tr[v][i];
		if (u == p)continue;
		int t = getcn(u, v);
		if (t > n >> 1)ok = false;
		s += t;
	}
	if (n - s > n >> 1)ok = false;
	if (ok)cn.push_back(v);
	return s;
}

int G;
void pl(int v, int p = 0){
	dp[v] = dp[p] + 1;
	gr[v] = G;
	f(i, 0, tr[v].size()){
		int u = tr[v][i];
		if (u == p)continue;
		pl(u, v);
	}
}

ll P(int x) { return (ll)x * (x - 1) >> 1; }

void solve(){
	scanf("%d", &n);
	f(i, 1, n + 1)tr[i].clear();
	f(j, 0, 2)f(i, 1, n + 1)dpfr[j][i] = 0;
	f(i, 2, n + 1){
		int t;
		scanf("%d", &t);
		tr[i].push_back(t);
		tr[t].push_back(i);
	}
	cn.clear();
	getcn();
	ll an = P(n);
	if ((int)cn.size() == 1){
		pl(cn[0]);
		f(i, 1, n + 1)++dpfr[0][dp[i]];
		f(i, 1, n + 1)an += P(dpfr[0][i]);
	}else {
		G = 0;
		dp[cn[1]] = 0;
		pl(cn[0], cn[1]);
		G = 1;
		dp[cn[0]] = 0;
		pl(cn[1], cn[0]);
		dp[cn[0]] = 1;
		f(i, 1, n + 1)++dpfr[gr[i]][dp[i]];
		f(i, 1, n + 1){
			an += P(dpfr[0][i]);
			an += P(dpfr[1][i]);
			an -= (ll)dpfr[0][i] * dpfr[1][i];
		}
	}
	printf("%lld\n", an);
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--)solve();
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 200000, md = 1e9 + 7;
int x[N], y[N], fc[N + 1], xt[N + 1], yt[N + 1];

void solve(){
	int n;
	scanf("%d", &n);
	n <<= 1;
	f(i, 0, n)scanf("%d%d", x + i, y + i);
	f(i, 0, n)xt[i] = x[i];
	sort(xt, xt + n);
	f(i, 0, n)yt[i] = y[i];
	sort(yt, yt + n);
	n >>= 1;
	if (xt[n - 1] == xt[n]) { printf("0\n"); return; }
	if (yt[n - 1] == yt[n]) { printf("0\n"); return; }
	n <<= 1;
	int a = 0, b = 0;
	f(i, 0, n)if (x[i] < xt[n >> 1])y[i] < yt[n >> 1] ? ++a : ++b;
	int an = (ll)fc[a] * fc[b] % md;
	printf("%d\n", an);
}

int main(){
	fc[0] = 1;
	f(i, 1, N + 1)fc[i] = (ll)fc[i - 1] * i % md;
	int t;
	scanf("%d", &t);
	while (t--)solve();
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 1000000, md = 1e9 + 7;
int fc[N + 1], inv[N + 1], fcin[N + 1];

void ad(int &x, int y) { if ((x += y) >= md)x -= md; }
void sb(int &x, int y) { if ((x -= y) < 0)x += md; }
int ch(int n, int r) { return (ll)fc[n] * fcin[r] % md * fcin[n - r] % md; }

void solve(){
	int n;
	scanf("%d", &n);
	int s = 0, an = 0;
	f(i, 0, n){
		ad(s, ch(n, i + 1));
		int t;
		scanf("%d", &t);
		ad(an, (ll)t * s % md);
		sb(s, ch(n, i));
	}
	printf("%d\n", an);
}

int main(){
	fc[0] = 1;
	f(i, 1, N + 1)fc[i] = (ll)fc[i - 1] * i % md;
	inv[1] = 1;
	f(i, 2, N + 1)inv[i] = md - md / i * (ll)inv[md % i] % md;
	fcin[0] = 1;
	f(i, 1, N + 1)fcin[i] = (ll)fcin[i - 1] * inv[i] % md;
	int t;
	scanf("%d", &t);
	while (t--)solve();
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back 
#define all(c) (c).begin(),(c).end()
int T,n,k;
multiset<int> A,B;

int main(){
	cin>>T;
	while(T--){
		A.clear();
		B.clear();
		cin>>n>>k;
		for(int x,i=0; i<n; ++i){
			scanf("%d",&x);
			A.insert(x);
		}
		for(int x,i=0; i<n; ++i){
			scanf("%d",&x);
			if(A.find(x)!=A.end())
				A.erase(A.find(x));
			else
				B.insert(x);
		}
		if(A.empty())
			puts("YES");
		else if(A.size()==1 && B.size()==1 && abs(*A.begin()-*B.begin())<=k)
			puts("YES");
		else
			puts("NO");
		
	}
	return 0;	
}

//#pragma comment(linker, "/STACK:16777216")

#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100000;
int n, res;
vector<vector<int> > g, o, v;
vector<vector<vector<int> > > cyc;
set<pair<int, int> > br;
int low[N], idx[N], dfs;
bool vis[N];
void DFS(int u, int p) {
	low[u] = idx[u] = ++dfs;
	for (auto v : g[u])
		if (!idx[v]) {
			DFS(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] > idx[u])
				br.insert({ min(u,v),max(u,v) });
		}
		else if (v != p)
			low[u] = min(low[u], idx[v]);
}
void DFS(int u) {
	if (vis[u])
		return;
	v.back().push_back(u);
	vis[u] = true;
	for (auto &w : g[u])
		DFS(w);
}
vector<vector<int> > options;
void findOptions(int u, int p) {
	if (g[u].size() > 3 && vis[u]) {
		if (options.back()[0] == options.back().back())
			options.back().pop_back();
		return;
	}
	if (p != -1 && g[u].size() == 3)
		return;
	vis[u] = true;
	for (auto v : g[u])
		if (v != p) {
			if (p == -1) {
				if (vis[v])
					continue;
				options.push_back(vector<int>());
				options.back().push_back(u);
			}
			options.back().push_back(v);
			findOptions(v, u);
		}
}
void findCycles(vector<int> &comp, vector<vector<int> > &cyc) {
	for (int i = 0; i < n; ++i)
		vis[i] = 0;
	for (auto u : comp) {
		if (vis[u])
			continue;
		cyc.push_back(vector<int>());
		queue<int> q;
		q.push(u);
		vis[u] = true;
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			cyc.back().push_back(u);
			for (auto v : g[u])
				if (!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
		}
		if (cyc.back().size() == 1)
			cyc.pop_back();
	}
	if (cyc.size() == 1) {
		int at = -1;
		for (auto x : cyc[0])
			if (g[x].size() == 4) {
				at = x;
				break;
			}
		if (at != -1) {
			for (int i = 0; i < n; ++i)
				vis[i] = 0;
			options.clear();
			findOptions(at, -1);
			assert(options.size() == 2);
			cyc = options;
		}
	}
	assert(cyc.size() <= 2);
}
int findClosest(const vector<int> &v, int x) {
	int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
	int cur = 1e9;
	if (idx != v.size())
		cur = v[idx] - x;
	if (idx != 0)
		cur = min(cur, x - v[idx - 1]);
	return cur;
}
int calc(int u, int p) {
	int ret = findClosest(cyc[0][0], u);
	for (auto v : g[u])
		if (v != p && br.find({ min(u,v),max(u,v) }) != br.end())
			ret = min(ret, calc(v, u));
	res = min(res, ret + findClosest(v[1], u));
	return ret;
}
int main()
{
	int t;
	scanf("%d", &t);
	int totalN=0;
	while (t--) {
		scanf("%d", &n);
		totalN+=n;
		g.clear();
		g.resize(n);
		if (n < 1 || n>100000) {
			puts("invalid n");
			exit(1);
		}
		set<pair<int, int> > e;
		for (int i = 1, a, b; i < n; ++i) {
			scanf("%d%d", &a, &b);
			if (a<1 || a>n || b<1 || b>n) {
				puts("Invalid (a, b)");
				exit(2);
			}
			if (a > b)
				swap(a, b);
			if (e.insert({ a,b }).second == false) {
				puts("Multiple edges");
				exit(3);
			}
			--a; --b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		for (int i = 0; i < n; ++i)
			vis[i] = 0;
		for (int i = 0; i < n; ++i)
			idx[i] = 0;
		dfs = 0;
		v.clear();
		cyc.clear();
		for (int i = 0; i < n; ++i)
			if (!vis[i]) {
				v.push_back(vector<int>());
				if (v.size() == 4)
					break;
				DFS(i);
			}
		if (v.size() == 4) {
			puts("-1");
			continue;
		}
		if (v.size() == 1) {
			puts("0");
			continue;
		}
		br.clear();
		for (int i = 0; i < n; ++i)
			if (!idx[i])
				DFS(i, -1);
		o = g;
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < g[i].size(); ++j)
				if (br.find({ min(i,g[i][j]),max(i,g[i][j]) }) != br.end()) {
					g[i][j] = g[i].back();
					g[i].pop_back();
					--j;
				}
		cyc.resize(v.size());
		for (int i = 0; i < v.size(); ++i)
			findCycles(v[i], cyc[i]);
		for (auto &cycles : cyc)
			for (auto &x : cycles) {
				sort(x.begin(), x.end());
				assert(x.size() >= 3);
			}
		res = 1e9;
		if (v.size() == 2) {
			if (cyc[0].empty()) {
				v[0].swap(v[1]);
				cyc[0].swap(cyc[1]);
			}
			sort(v[1].begin(), v[1].end());
			g = o;
			for (auto x : cyc[0][0])
				calc(x, -1);
			printf("%d\n", res);
			continue;
		}
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				if (cyc[j].size() < cyc[j + 1].size()) {
					v[j].swap(v[j + 1]);
					cyc[j].swap(cyc[j + 1]);
				}
		if (cyc[0].size() == 2) {
			pair<int, int> A(1e9, 1e9), B(1e9, 1e9);
			for (int it = 1; it <= 2; ++it) {
				for (int i = 0; i < v[it].size(); ++i) {
					A.first = min(A.first, findClosest(cyc[0][0], v[it][i]));
					A.second = min(A.second, findClosest(cyc[0][1], v[it][i]));
				}
				swap(A, B);
			}
			res = min(A.first + B.second, A.second + B.first);
			printf("%d\n", res);
			continue;
		}
		if (!cyc[1].empty()) {
			for (int i = 0; i < 2; ++i) {
				int curA = 1e9;
				for (auto x : v[2])
					curA = min(curA, findClosest(cyc[i][0], x));
				int curB = 1e9;
				for (auto x : v[2])
					curB = min(curB, findClosest(cyc[!i][0], x));
				for (auto x : v[i])
					curB = min(curB, findClosest(cyc[!i][0], x));
				res = min(res, curA + curB);
			}
			printf("%d\n", res);
			continue;
		}
		options.clear();
		for (int i = 0; i < n; ++i)
			vis[i] = 0;
		for (auto u : cyc[0][0])
			if (g[u].size() > 2) {
				findOptions(u, -1);
				break;
			}
		assert(options.size() == 3);
		for (auto &x : options)
			sort(x.begin(), x.end());
		int cur[2][3] = {};
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 3; ++j) {
				cur[i][j] = 1e9;
				for (auto x : v[i + 1])
					cur[i][j] = min(cur[i][j], findClosest(options[j], x));
			}
		for (int i = 0; i < 3; ++i) {
			res = min(res, cur[0][i] + min(cur[1][!i], cur[1][3 - i - !i]));
			res = min(res, cur[1][i] + min(cur[0][!i], cur[0][3 - i - !i]));
		}
		printf("%d\n", res);
	}
	cerr<<totalN<<endl;
	assert(totalN<=5000000);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
typedef vector<pair<int, int> > vp;

int const N = 100000, inf = 1e9;
vp g[N + 1];
vector<int> cy[N];
int vis[N + 1], vs = 1, n;

struct CM{
	vector<set<int> > v;
	set<int> all;
	CM(){}
	bool operator <(CM const &o)const { return v.size() > o.v.size(); }
	bool in(int x) { return all.find(x) != all.end(); }
};

bool in(int x, set<int> const &st) { return st.find(x) != st.end(); }

int getCost(int x, set<int> const &st){
	set<int>::iterator it = st.lower_bound(x);
	int an = it == st.end() ? inf : *it - x;
	if (it == st.begin())return an;
	--it;
	return min(an, x - *it);
}

int getCost(set<int> const &a, set<int> const &b){
	int an = inf;
	set<int>::iterator ita = a.begin(), itb = b.begin();
	while (ita != a.end() && itb != b.end()){
		an = min(an, abs(*ita - *itb));
		if (*ita < *itb)++ita; else ++itb;
	}
	return an;
}

vector<CM> cm;
map<vector<int>, int> mp;

int getId(vector<int> const &v){
	map<vector<int>, int>::iterator it = mp.find(v);
	if (it == mp.end()){
		int an = mp.size();
		cm.back().v.push_back(set<int>());
		return mp[v] = an;
	}
	return it->second;
}

int C;
vp build(int v, int p = 0){
	vp c;
	vis[v] = 0;
	f(i, 0, g[v].size()){
		int u = g[v][i].first;
		if (u == p)continue;
		if (vis[u] == 0)c.push_back(make_pair(C, u)), cy[g[v][i].second].push_back(C++);
		else {
			vp t = build(u, v);
			while (t.size())c.push_back(t.back()), cy[g[v][i].second].push_back(t.back().first), t.pop_back();
		}
	}
	f(i, 0, c.size())if (c[i].second == v)c.erase(c.begin() + i), --i;
	vis[v] = 1;
	return c;
}

void geted(int v){
	vis[v] = 0;
	cm.back().all.insert(v);
	f(i, 0, g[v].size()){
		int u = g[v][i].first;
		int id = g[v][i].second;
		if (!cy[id].empty()){
			sort(cy[id].begin(), cy[id].end());
			int cid = getId(cy[id]);
			cm.back().v[cid].insert(v);
			cm.back().v[cid].insert(u);
			cy[id].clear();
		}
		if (vis[u] == 0)continue;
		geted(u);
	}
}

void visi(int v){
	if (vis[v] == vs)return;
	vis[v] = vs;
	f(i, 0, g[v].size())visi(g[v][i].first);
}

int go(int v, int p, int mn = inf){
	int an = mn + getCost(v, cm[0].v[0]);
	mn = min(mn, getCost(v, cm[1].all));
	f(i, 0, g[v].size()){
		int u = g[v][i].first;
		if (u == p)continue;
		an = min(an, go(u, v, mn));
	}
	return an;
}

int solve(){
	scanf("%d", &n);
	f(i, 1, n + 1)g[i].clear();
	f(i, 1, n)cy[i].clear();
	f(i, 1, n){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(make_pair(b, i));
		g[b].push_back(make_pair(a, i));
	}
	int cmp = 0;
	f(i, 1, n + 1)vis[i] = inf;
	f(i, 1, n + 1)if (vis[i] > vs)++vs, visi(i), ++cmp;
	if (cmp == 1)return 0;
	if (cmp > 3)return -1;
	cm.clear();
	f(i, 1, n + 1)if (vis[i] > 1){
		cm.push_back(CM());
		mp.clear();
		build(i);
		geted(i);
	}
	sort(cm.begin(), cm.end());
	int an = inf;
	if (cmp == 2){
		an = getCost(cm[0].v[0], cm[1].all);
		f(i, 1, n + 1)if (in(i, cm[0].v[0]))f(j, 0, g[i].size())if (!in(g[i][j].first, cm[0].v[0]))an = min(an, go(g[i][j].first, i));
		return an;
	}
	if (cm[0].v.size() > 1){
		f(i, 0, cm[0].v.size())f(j, 0, cm[0].v.size())if (i != j)an = min(an, getCost(cm[0].v[i], cm[1].all) + getCost(cm[0].v[j], cm[2].all));
		return an;
	}
	int a = getCost(cm[0].v[0], cm[1].all);
	int b = getCost(cm[0].v[0], cm[2].all);
	int c = getCost(cm[1].v[0], cm[0].all);
	int d = getCost(cm[1].v[0], cm[2].all);
	return min(b + min(c, d), d + min(a, b));
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--)printf("%d\n", solve());
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 200000;
double const eps = 1e-7;
int n, a, q;
long double an[N];

bool eq(double a, double b) { return abs(a - b) <= eps; }

struct V{
	double x, y;
	V(double a = 0.0, double b = 0.0):x(a), y(b) {}
	void sc() { scanf("%lf%lf", &x, &y); }
	double operator |(V const &o)const {
		return x * o.y - o.x * y;
	}
	bool operator <(V const &o)const {
		if (eq(x, o.x))return y < o.y;
		return x < o.x;
	}
	V operator -(V const &o)const { return V(x - o.x, y - o.y); }
	void pr() { printf("%lf %lf\n", x, y); }
}st[N];

pair<V, int> qu[N];

bool cmpr(V const &a, V const &b){
	V v1 = a - st[0], v2 = b - st[0];
	return (v1 | v2) < -eps;
}	


vector<V> ch;
void getCh(){
	sort(st + 1, st + n, cmpr);
	ch.push_back(st[0]);
	f(i, 1, n){
		while ((int)ch.size() > 1 && (st[i] - ch.back() | ch.back() - ch[ch.size() - 2]) < eps)ch.pop_back();
		ch.push_back(st[i]);
	}
}

double getx(double xs, double z, double xq){
	return xs + z / (z + a) * (xq - xs);
}

int left(int x) { return x ? x - 1 : ch.size() - 1; }
int right(int x) { return x + 1 == (int)ch.size() ? 0 : x + 1; }

void solve(){
	scanf("%d%d", &n, &a);
	f(i, 0, n)st[i].sc();
	double mnz = st[0].y, mxz = st[0].y;
	f(i, 1, n){
		mnz = min(mnz, st[i].y);
		mxz = max(mxz, st[i].y);
	}
	f(i, 0, n)st[i].y = a - st[i].y;
	sort(st, st + n);
	ch.clear();
	getCh();
	scanf("%d", &q);
	f(i, 0, q){
		qu[i].first.sc();
		qu[i].second = i;
	}
	sort(qu, qu + q);
	int lp = 0, rp = 0;
	f(i, 0, ch.size())ch[i].y = a - ch[i].y;
	while (ch[right(rp)].y < ch[rp].y)rp = right(rp);
	while (ch[left(lp)].y > ch[lp].y)lp = left(lp);
	f(i, 0, q){
		while (true){
			int ni = right(lp);
			if (getx(ch[ni].x, ch[ni].y, qu[i].first.x) < getx(ch[lp].x, ch[lp].y, qu[i].first.x))lp = ni;
			else break;
		}
		while (true){
			int ni = right(rp);
			if (getx(ch[ni].x, ch[ni].y, qu[i].first.x) > getx(ch[rp].x, ch[rp].y, qu[i].first.x))rp = ni;
			else break;
		}
		double x = abs(getx(ch[rp].x, ch[rp].y, qu[i].first.x) - getx(ch[lp].x, ch[lp].y, qu[i].first.x));
		double y = getx(0, mxz, qu[i].first.y) - getx(0, mnz, qu[i].first.y);
		an[qu[i].second] = (long double) x * y;;
	}
	f(i, 0, q)printf("%.10lf\n", (double)an[i]);
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--)solve();
}

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
typedef pair<int,int> pii;
typedef long long ll;
const int N = 10000+1;

int n , q,T;
vector<pii> g[N];
ll ans = 0,in[N],out[N];

void dfs(int u , int p, int w){
	for(auto v : g[u]){
		if(v.first==p)continue;
		dfs(v.first,u,v.second);
		in[u] += in[v.first];
		out[u] += out[v.first];
	}
	ans += 1ll*abs(in[u]-out[u])*w;
}
int main(){
	cin >> T;
	while(T--){
		cin >> n;
		ans = 0;
		for (int i = 1; i <= n; ++i){
			g[i].clear();
			in[i] = out[i] = 0;
		}
		for (int u , v,w , i = 0 ; i < n-1 ; ++i){
			scanf("%d%d%d",&u,&v,&w);
			g[u].pb(mp(v,w));
			g[v].pb(mp(u,w));
		}
		cin >> q;
		for(int u , v , i = 0 ; i < q ; ++i){
			scanf("%d%d",&u,&v);
			out[u]++;
			in[v]++;
		}
		dfs(1,-1,0);
		cout << ans << endl;
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int N = 1001;
int n , l , dp[N][N],T;

pii a[N];

int calc(int idx , int time){
	if(idx > n || time > l+1)return -N;
	if(idx == n && time == l+1)return 0;
	int &ret = dp[idx][time];
	if(ret != -1)return ret;
	ret = max(calc(idx,time+1),calc(idx+1,time));
	if(time >= a[idx].first)
		ret = max(ret,1+calc(idx+1,time+a[idx].second));
	return ret;
}
int main(){
	cin >> T;
	while(T--){
		memset(dp,-1,sizeof dp);
		cin >> n >> l;
		for (int i = 0; i < n; ++i)scanf("%d%d",&a[i].first,&a[i].second);
		printf("%d\n",calc(0,1));
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
int n , m , r,T;

vector< vector<int> > g;
multiset< pii > hv[100002];
multiset<pii> cur;

int
 ALL_PEOPLE = 0;
bool check(int md){
	cur.clear();
	for(int i = 0 ; i < m ; ++i)hv[i].clear();
	for(int j = 0 ; j < md ; ++j)cur.insert(make_pair(-2,m));

	for(int j = 0 ; j < n ; ++j){
		for (int i = 0; i < m; ++i){
			int rem = g[i][j];
			vector<int> nw;
			while(rem > 0){
				assert(cur.size() == md);
				if(hv[i].size()){
					pii fr = *--hv[i].end();
					hv[i].erase(--hv[i].end());
					cur.erase(cur.find(fr));
					cur.insert(make_pair(j,i));
					nw.push_back(j);
				}else{
					pii em = *cur.begin();
					if(em.first >= j-1)return false;
					cur.erase(cur.begin());
					if(em.second != m)
						hv[em.second].erase(hv[em.second].find(em));
					cur.insert(make_pair(j,i));
					nw.push_back(j);
				}
				rem -= r;
			}
			for(int k = 0 ; k < nw.size();++k){
				hv[i].insert(make_pair(nw[k],i));
			}
		}
	}
	return 1;
}

int main(){
//	freopen("2.in","r",stdin);
//	freopen("2.out","w",stdout);
	cin >> T;
	while(T--){
		scanf("%d%d%d",&m,&n,&r);
		g.clear();
		g.resize(m);
		int total = 0;
		for (int i = 0; i < m; ++i){
			g[i].resize(n);
			for(int j = 0 ; j < n ; ++j){
				scanf("%d",&g[i][j]);
				total += g[i][j];
			}
		}
		ALL_PEOPLE += total;
		int lo = 1, hi = total,best = -1;
		while(lo <= hi){
			int md = (lo + hi)/2;
			if(check(md)){
				best = md;
				hi = md-1;
			}else{
				lo=md+1;
			}
		}
		cout << best << endl;
	}
	//cout << "ALL PEOPLE = " << ALL_PEOPLE << endl;

	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back 
#define all(c) (c).begin(),(c).end()
int n,m,cmp[2*N],t;
vi g[2*N],rg[2*N];
bool vis[2*N];

int Not(int x){
	return x>=n?x-n:x+n;
}

void addEdge(int a, int b){
	g[Not(b)].pb(a);
	g[Not(a)].pb(b);
	rg[a].pb(Not(b));
	rg[b].pb(Not(a));
}

stack<int> st;
void dfs(int u, vi g[N], int cc=-1){
	vis[u]=1;
	for(int i=0; i<g[u].size(); ++i)
		if(!vis[g[u][i]])
			dfs(g[u][i], g, cc);
	if(cc==-1){
		st.push(u);
	}else{
		cmp[u]=cc;
	}
}

void get(int &x, int l, int r){
	assert(scanf("%d",&x)==1);
	assert(x>=l && x<=r);
}

int main(){
	get(t,1,1000);
	while(t--){
		get(n, 1, 100000);
		get(m, 0, 100000);
		for(int a,b,c,i=0; i<m; ++i){
			get(a,1,n);
			get(b,1,n);
			assert(a!=b);
			get(c,0,1);
			--a;--b;
			if(c)
				addEdge(Not(a), Not(b));
			addEdge(a, b);
		}
		for(int i=0; i<2*n; ++i)
			vis[i]=0;
		for(int i=0; i<2*n; ++i)
			if(!vis[i])
				dfs(i,g);
		for(int i=0; i<2*n; ++i)
			vis[i]=0;
		int cc=0;
		while(!st.empty()){
			int u=st.top();
			st.pop();
			if(vis[u])continue;
			dfs(u, rg, cc++);
		}
		bool win=1;
		for(int i=0; i<n && win; ++i){
			if(cmp[i]==cmp[Not(i)])
				win=0;
		}
		if(win)
			puts("YES");
		else
			puts("NO");

		for(int i=0; i<2*n; ++i){
			g[i].clear();
			rg[i].clear();
		}
	}
	return 0;	
}