for _ in range(int(input())):
    n, m = map(int, input().split())
    for _ in range(m):
        input()
    print("NO" if n == m else "YES")

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    forn(_, t){
        int n, m;
        scanf("%d%d", &n, &m);
        vector<pair<int, int>> a(m);
        forn(i, m){
            scanf("%d%d", &a[i].first, &a[i].second);
            --a[i].first, --a[i].second;
        }
        bool ans = false;
        forn(i, m) forn(x, n) forn(y, n) if ((x == a[i].first) ^ (y == a[i].second)){
            bool ok = true;
            forn(j, m) if (i != j){
                ok &= x != a[j].first && y != a[j].second;
            }
            ans |= ok;
        }
        puts(ans ? "YES" : "NO");
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(' ').map { it.toLong() }
        val b = readLine()!!.split(' ').map { it.toLong() }

        println(a.sum() + b.sum() - b.maxOrNull()!!)
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int ans = 0;
    for (int k = 1; k <= n; ++k) {
      multiset<int> s(a.begin(), a.end());
      for (int i = 0; i < k; ++i) {
        auto it = s.upper_bound(k - i);
        if (it == s.begin()) break;
        s.erase(--it);
        if (!s.empty()) {
          int x = *s.begin();
          s.erase(s.begin());
          s.insert(x + k - i);
        }
      }
      if (s.size() + k == n) ans = k;
    }
    cout << ans << '\n';
  }
}

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

const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}   

int sub(int x, int y)
{
    return add(x, -y);
}   

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

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

int main()
{
    int n;
    long long m;
    cin >> n >> m;
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = add(ans, binpow(m % MOD, i));
    long long cur = 1;
    int cnt = 1;
    for(int i = 1; i <= n; i++)
    {
        if(cur > m) continue;
        if(prime(i)) cur *= i;
        cnt = mul(cnt, (m / cur) % MOD);
        ans = sub(ans, cnt);
    }
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, -1, 1, -1, 1};

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (auto &it : s) cin >> it;
    
    auto in = [&](int x, int y) {
      return 0 <= x && x < n && 0 <= y && y < m;
    };
    
    auto can = [&](int x, int y) {
      if (!in(x, y)) return false;
      for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (in(nx, ny) && s[nx][ny] == '#')
          return false;
      }
      return true;
    };
    
    vector<vector<int>> d(n, vector<int>(m, INF)), p(n, vector<int>(m));
    deque<pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        if (s[i][0] == '#') {
          d[i][0] = 0;
          q.push_front({i, 0});
        } else if (can(i, 0)) {
          d[i][0] = 1;
          q.push_back({i, 0});
        }
    }
    
    while (!q.empty()) {
      auto [x, y] = q.front();
      q.pop_front();
      for (int i = 4; i < 8; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (!can(nx, ny)) continue;
        int w = (s[nx][ny] != '#');
        if (d[nx][ny] > d[x][y] + w) {
          d[nx][ny] = d[x][y] + w;
          p[nx][ny] = i;
          if (w) q.push_back({nx, ny});
          else q.push_front({nx, ny});
        }
      }
    }
    
    int x = 0, y = m - 1;
    for (int i = 0; i < n; ++i) if (d[x][y] > d[i][y])
      x = i;
    if (d[x][y] == INF) {
      cout << "NO\n";
      continue;
    }
    while (true) {
      s[x][y] = '#';
      int i = p[x][y];
      if (!i) break;
      x -= dx[i];
      y -= dy[i];
    }
    cout << "YES\n";
    for (auto it : s) cout << it << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

typedef long long li;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);

const int N = int(2e5) + 55;
const int LOG = 18;

int n;
vector<int> g[N];

inline bool read() {
    if(!(cin >> n))
        return false;
    fore (i, 0, n - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        
        g[u].push_back(v);
        g[v].push_back(u);
    }
    return true;
}

int p[LOG][N];
int tin[N], tout[N], T = 0;

void build(int v, int pr) {
    tin[v] = T++;
    p[0][v] = pr;
    fore (pw, 1, LOG)
        p[pw][v] = p[pw - 1][p[pw - 1][v]];
    
    for (int to : g[v]) {
        if (to == pr)
            continue;
        build(to, v);
    }
    tout[v] = T;
}

bool inside(int l, int v) {
    return tin[l] <= tin[v] && tout[v] <= tout[l];
}

int lca(int u, int v) {
    if (inside(u, v))
        return u;
    if (inside(v, u))
        return v;
    
    for (int pw = LOG - 1; pw >= 0; pw--) {
        if (!inside(p[pw][u], v))
            u = p[pw][u];
    }
    return p[0][u];
}

const int D = 21;
struct Fenwick {
    int n;
    vector<int> F;
    void init(int nn) {
        n = nn;
        F.assign(n, 0);
    }
    
    void add(int pos, int val) {
        for (; pos < n; pos |= pos + 1)
            F[pos] += val;
    }
    int sum(int pos) {
        int ans = 0;
        for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
            ans += F[pos];
        return ans;
    }
    int getSum(int l, int r) {
        return sum(r - 1) - sum(l - 1);
    }
};

struct DS {
    Fenwick f;
    void init(int n) {
        f.init(n);
    }
    
    void addPath(int v, int l, int k) {
        f.add(tin[v], +k);
        f.add(tin[l], -k);
    }
    int getVertex(int v) {
        return f.getSum(tin[v], tout[v]);
    }
    
    void addVertex(int v, int k) {
        f.add(tin[v], +k);
        if (p[0][v] != v)
            f.add(tin[p[0][v]], -k);
    }
};

DS t[D];

inline void solve() {
    fore (i, 0, D) {
        g[n - 1 + i].push_back(n + i);
        g[n + i].push_back(n - 1 + i);
    }
    int root = n + D - 1;
    
    build(root, root);
    fore (i, 0, D)
        t[i].init(root + 1);
    
    int m; cin >> m;
    fore(_, 0, m) {
        int tp; cin >> tp;
        if (tp == 1) {
            int v; cin >> v;
            v--;
            
            int ans = 0;
            for (int i = 0, cur = v; i < D; i++, cur = p[0][cur])
                ans += t[i].getVertex(cur);
            cout << ans << endl;
        } 
        else {
            assert(tp == 2);

            int u, v, k, d;
            cin >> u >> v >> k >> d;
            u--, v--;
            
            int l = lca(u, v);
            
            if (u != l)
                t[d].addPath(u, l, k);
            if (v != l)
                t[d].addPath(v, l, k);
            
            for (int i = 0; i <= d; i++, l = p[0][l]) {
                t[d - i].addVertex(l, k);
                if (d - i > 0)
                    t[d - i - 1].addVertex(l, k);
            }
        }
    }
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

for _ in range(int(input())):
	n = int(input())
	a = set(map(int, input().split()))
	ans = 0
	for i in range(10000):
		num = str(i)
		num = (4 - len(num)) * '0' + num
		used = set(num)
		if len(used) != 2:
			continue
		d1 = int(used.pop())
		d2 = int(used.pop())
		if (not d1 in a) and (not d2 in a) and num.count(num[0]) == 2:
			ans += 1
	print(ans)

#include <bits/stdc++.h>

using namespace std;

int n;

inline void read() {	
    cin >> n;
    int x;
    for (int i = 0; i < n; ++i)
        cin >> x;
}

inline int fac(int n) {
    int res = 1;
    for (int i = 2; i <= n; i++) {
        res *= i;
    }
    return res;
}

inline int c(int n, int k) {
    return fac(n) / fac(k) / fac(n - k);
}

inline void solve() {
    cout << c(10 - n, 2) * c(4, 2) << endl;
}

int main () {
    int t;
    cin >> t;
    while (t--){
        read();
        solve();
    }
}

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

void solve() 
{
    int n;
    cin >> n;
    cout << 1;
    for(int i = n; i >= 2; i--)
        cout << " " << i;
    cout << endl;
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

for _ in range(int(input())):
	n = int(input())
	s = '0' + input()
	a = [0] + list(map(int, input().split()))
	ans = 0
	i = 0
	while i <= n:
		mn = a[i]
		sm = a[i]
		j = i + 1
		while j <= n and s[j] == '1':
			mn = min(mn, a[j])
			sm += a[j]
			j += 1
		ans += sm - mn
		i = j
	print(ans)

#include<bits/stdc++.h>

using namespace std;

char buf[1000043];

string normalize(const string& v)
{
    int cnt = 0;
    while(cnt < v.size() && v[cnt] == '0') cnt++;
    if(cnt == v.size()) return "0";
    return v.substr(cnt, int(v.size()) - cnt);
}

string operator |(const string& a, const string& b)
{
    int sz = max(a.size(), b.size());
    string ans(sz, '0');
    for(int i = 0; i < a.size(); i++)
        if(a[i] == '1') ans[i + sz - int(a.size())] = '1';
    for(int i = 0; i < b.size(); i++)
        if(b[i] == '1') ans[i + sz - int(b.size())] = '1';    
    return normalize(ans);
}

bool better(const string& a, const string& b)
{
    if(a.size() != b.size()) return a.size() > b.size();
    return a > b;
}

int main()
{
    int n;
    scanf("%d", &n);
    string s;
    scanf("%s", buf);
    s = buf;
    string ans = s | s;
    int pos1 = s.find("1");
    if(pos1 != string::npos)
    {
        int pos2 = s.find("0", pos1);
        if(pos2 != string::npos)
        {
            int cur = pos1;
            int not_needed = 0;
            while(true)
            {                
                if(cur == n || (s[cur] == '1' && cur > pos2)) break;
                string nw = s | s.substr(pos1, n - pos1 - not_needed);
                if(better(nw, ans)) ans = nw;
                cur++;
                not_needed++;
            }
        }
    }
    puts(ans.c_str());
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const long long INF64 = 1e18;

int main() {
	vector<int> ps(2);
	vector<long long> ts(2);
	int h, s;
	forn(i, 2) scanf("%d%lld", &ps[i], &ts[i]);
	scanf("%d%d", &h, &s);
	long long ans = INF64;
	vector<long long> dp(h + 1, INF64);
	dp[0] = 0;
	forn(i, h) for (int j = 1; j <= h - i; ++j) forn(k, 2){
		int ni = min((long long)h, i + j * (ps[k] - s) + j * ts[k] / ts[k ^ 1] * (ps[k ^ 1] - s));
		if (ni == h)
			ans = min(ans, dp[i] + j * ts[k]);
		if (j * ts[k] >= ts[k ^ 1]){
			ni = min((long long)h, i + (j - 1) * (ps[k] - s) + (j * ts[k] / ts[k ^ 1] - 1) * (ps[k ^ 1] - s) + (ps[0] + ps[1] - s));
			dp[ni] = min(dp[ni], dp[i] + j * ts[k]);
		}
	}
	ans = min(ans, dp[h]);
	printf("%lld\n", ans);
}

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;

typedef array<int, 2> vec;
typedef array<vec, 2> mat;

const int MOD = 998244353;

mat operator*(const mat& a, const mat& b)
{
    mat c;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            c[i][j] = 0;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                c[i][k] = (a[i][j] * 1ll * b[j][k] + c[i][k]) % MOD;
    return c;
}

mat ZERO = {vec({3, 0}), vec({1, 2})};
mat ONE = {vec({1, 2}), vec({1, 2})};

mat t[4 * N];

void recalc(int v)
{
    t[v] = t[v * 2 + 1] * t[v * 2 + 2];    
}

void build(int v, int l, int r)
{
    if(l == r - 1)
    {            
        t[v] = ZERO;                       
    }
    else
    {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
        recalc(v);               
    }
}

void upd(int v, int l, int r, int pos, int val)
{
    if(l == r - 1)
    {
        if(val == 0) t[v] = ZERO;
        else t[v] = ONE;
    }
    else
    {
        int m = (l + r) / 2;
        if(pos < m) upd(v * 2 + 1, l, m, pos, val);
        else upd(v * 2 + 2, m, r, pos, val);
        recalc(v);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> v(N);
    for(int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        v[l].push_back(make_pair(1, i));
        v[r + 1].push_back(make_pair(0, i));
    }    
    build(0, 0, n - 1);
    int cur = 0;
    int ans = 0;
    for(int i = 0; i <= 300000; i++)
    {
        for(auto x : v[i])
        {
            if(x.second == 0) cur = x.first;
            else upd(0, 0, n - 1, x.second - 1, x.first);
        }
        ans = (ans + t[0][cur][1]) % MOD;
    }
    cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

int sub(int x, int y)
{
    return add(x, MOD - y);
}

int expected(int mask)
{
    if(mask & 2) return 0;
    return 1;
}

int last_bit(int x)
{
    if(x == 0) return -1;
    return x - (x & (x - 1));
}

bool go(int& a, int x)
{
    if(expected(a) != x)
    {
        a = 1 << x;
        return false;    
    }
    a ^= (1 << x);
    while(true)
    {
        int b = last_bit(a);
        int c = last_bit(a - b);
        if(c == 2 * b) a += b;
        else break;
    }
    return true;
}

bool is_fib(int a)
{
    return a == last_bit(a);
}

vector<pair<int, int>> go(const vector<pair<int, int>>& a, int x)
{
    vector<pair<int, int>> nw;
    for(auto b : a)
    {
        int cost = b.first;
        int seqn = b.second;
        if(go(seqn, x)) nw.push_back(make_pair(cost, seqn));
    }
    return nw;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int last = 1, sum = 1;
    vector<pair<int, int>> w;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(auto x : s)
        {
            int c = x - '0';
            int ndp = sub(sum, last);
            w = go(w, c);
            for(int j = 0; j < w.size(); j++)
            {
                if(is_fib(w[j].second))
                    ndp = sub(ndp, w[j].first);
            }
            if(c == 1) w.push_back(make_pair(last, 2));
            sum = add(sum, ndp);
            last = ndp;
            assert(w.size() <= 60);
        }
        cout << last << endl;
    }
}

for _ in range(int(input())):
	n, m = map(int, input().split())
	print(n // 2 + 1, m // 2 + 1)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n, m;
		scanf("%d%d", &n, &m);
		int svx = 1, svy = 1;
		for (int x = 1; x <= n; ++x){
			for (int y = 1; y <= m; ++y){
				bool ok = true;
				for (int dx : {-2, -1, 1, 2}){
					for (int dy : {-2, -1, 1, 2}){
						if (abs(dx * dy) != 2) continue;
						if (1 <= x + dx && x + dx <= n && 1 <= y + dy && y + dy <= m)
							ok = false;
					}
				}
				if (ok){
					svx = x;
					svy = y;
				}
			}
		}
		printf("%d %d\n", svx, svy);
	}
}

for _ in range(int(input())):
	n = int(input())
	ans = [0]
	for x in map(int, input().split()):
		if x != 0 and ans[-1] - x >= 0:
			print(-1)
			break
		else:
			ans.append(ans[-1] + x)
	else:
		print(*ans[1:])

#include<bits/stdc++.h>

using namespace std;

long long dp[65][65][3];

void solve(int n)
{
    memset(dp, 0, sizeof dp);
    int k = n / 2;
    dp[0][0][2] = 1;
    for(int i = 0; i <= k; i++)
        for(int j = 0; j <= k; j++)
            for(int t = 0; t <= 2; t++)
            {
                int turn = (i + j) % 4;
                if (turn == 0 || turn == 3)
                {
                    if(i < k) dp[i + 1][j][t == 2 ? 0 : t] += dp[i][j][t];
                    if(j < k) dp[i][j + 1][t] += dp[i][j][t];
                }
                else
                {
                    if(i < k) dp[i + 1][j][t] += dp[i][j][t];
                    if(j < k) dp[i][j + 1][t == 2 ? 1 : t] += dp[i][j][t];
                }
            }
    for(int i = 0; i < 3; i++)
        cout << dp[k][k][i] % 998244353 << " ";
    cout << endl;
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        solve(n);
    }
}

def fact(n):
    return 1 if n == 0 else n * fact(n - 1)

def choose(n, k):
    return fact(n) // fact(k) // fact(n - k)

def calc(n):
    if n == 2:
        return [1, 0, 1]
    else:
        a = calc(n - 2)
        return [choose(n - 1, n // 2) + a[1], choose(n - 2, n // 2) + a[0], 1]

t = int(input())
for i in range(t):
    mod = 998244353
    n = int(input())
    a = calc(n)
    a = list(map(lambda x: x % mod, a))
    print(*a)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int n;
vector<vector<int>> g;

vector<int> st;
vector<int> pd;

void init(int v, int d){
	st.push_back(v);
	if (int(st.size()) - d >= 0)
		pd[v] = st[st.size() - d];
	for (int u : g[v])
		init(u, d);
	st.pop_back();
}

vector<char> used;

void dfs(int v){
	used[v] = true;
	for (int u : g[v]) if (!used[u])
		dfs(u);
}

int get(int d){
	pd.assign(n, -1);
	init(0, d);
	
	vector<int> ord, h(n);
	queue<int> q;
	q.push(0);
	while (!q.empty()){
		int v = q.front();
		q.pop();
		ord.push_back(v);
		for (int u : g[v]){
			q.push(u);
			h[u] = h[v] + 1;
		}
	}
	reverse(ord.begin(), ord.end());
	
	used.assign(n, 0);
	int res = 0;
	for (int v : ord) if (!used[v] && h[v] > d){
		++res;
		dfs(pd[v]);
	}
	
	return res;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int k;
		scanf("%d%d", &n, &k);
		g.assign(n, vector<int>());
		for (int i = 1; i < n; ++i){
			int p;
			scanf("%d", &p);
			--p;
			g[p].push_back(i);
		}
		int l = 1, r = n - 1;
		int ans = n;
		while (l <= r){
			int m = (l + r) / 2;
			if (get(m) <= k){
				ans = m;
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int INF = 1e9;

int main(){
	int n;
	cin >> n;
	vector<string> s(2);
	forn(i, 2) cin >> s[i];
	vector<array<array<int, 2>, 2>> dp(n + 1);
	forn(i, n + 1) forn(j, 2) forn(k, 2) dp[i][j][k] = -INF;
	dp[0][0][s[1][0] == '1'] = s[1][0] == '1';
	dp[0][0][0] = 0;
	forn(i, n - 1) forn(j, 2){
		int nxtj = s[j][i + 1] == '1';
		int nxtj1 = s[j ^ 1][i + 1] == '1';
		dp[i + 1][j ^ 1][0] = max(dp[i + 1][j ^ 1][0], dp[i][j][1] + nxtj1);
		dp[i + 1][j][nxtj1] = max(dp[i + 1][j][nxtj1], dp[i][j][0] + nxtj1 + nxtj);
		dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0] + nxtj);
	}
	cout << max({dp[n - 1][0][0], dp[n - 1][0][1], dp[n - 1][1][0], dp[n - 1][1][1]}) << '\n';
}

#include<bits/stdc++.h>

using namespace std;

const int N = 10043;
const int K = 12;

int tsz = 0;
int trie[N][K];
int aut[N][K];
int lnk[N];
int p[N];
int pchar[N];
int cost[N];
int ncost[N];

int newNode()
{
    lnk[tsz] = -1;
    ncost[tsz] = -1;
    cost[tsz] = 0;
    for(int i = 0; i < K; i++)
    {
        trie[tsz][i] = aut[tsz][i] = -1;
    }
    return tsz++;
}

int nxt(int x, int y)
{                                 
    if(trie[x][y] == -1) 
    {
        trie[x][y] = newNode();
        pchar[trie[x][y]] = y;
        p[trie[x][y]] = x;
    }
    return trie[x][y];
}

int go(int x, int y);

int get_lnk(int x)
{
    if(lnk[x] != -1) return lnk[x];
    int& d = lnk[x];
    if(x == 0 || p[x] == 0) return d = 0;
    return d = go(get_lnk(p[x]), pchar[x]);    
}

int go(int x, int y)
{
    if(aut[x][y] != -1) return aut[x][y];
    int& d = aut[x][y];
    if(trie[x][y] != -1) return d = trie[x][y];
    if(x == 0) return d = 0;
    return d = go(get_lnk(x), y);
}

void add(string s, int c)
{
    int cur = 0;
    for(auto x : s) cur = nxt(cur, x - 'a');
    cost[cur] += c;     
} 

int calc(int x)
{
    if(ncost[x] != -1) return ncost[x];
    ncost[x] = cost[x];
    int y = get_lnk(x);
    if(y != x) ncost[x] += calc(y);
    return ncost[x];
}

int main()
{
    int root = newNode();
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        string s;
        int x;
        cin >> x >> s;
        map<char, set<char>> adj;
        for(int j = 0; j + 1 < s.size(); j++)
        {
            adj[s[j]].insert(s[j + 1]);
            adj[s[j + 1]].insert(s[j]);
        }
        bool bad = false;
        string res = "";
        char c;
        for(c = 'a'; c <= 'l'; c++)
        {
            if(!adj.count(c)) continue;
            if(adj[c].size() >= 3)
                bad = true;
            if(adj[c].size() == 1)
                break;
        }
        if(c == 'm' || bad) continue;
        res.push_back(c);
        while(adj[c].size() > 0)
        {
            char d = *adj[c].begin();
            adj[c].erase(d);
            adj[d].erase(c);
            c = d;
            res.push_back(c);  
        }
        bad |= adj.size() != res.size();
        map<char, int> pos;
        for(int i = 0; i < res.size(); i++)
            pos[res[i]] = i;
        for(int i = 0; i + 1 < s.size(); i++)
            bad |= abs(pos[s[i]] - pos[s[i + 1]]) > 1;
        if(bad) continue;
        add(res, x);
        reverse(res.begin(), res.end());
        add(res, x);
    }  
    int INF = 1e9;
    int K = 12;
    vector<vector<int>> dp(1 << K, vector<int>(tsz + 1, -INF));
    vector<vector<pair<int, int>>> pdp(1 << K, vector<pair<int, int>>(tsz + 1));
    dp[0][0] = 0;
    for(int i = 0; i < (1 << K); i++)
        for(int j = 0; j <= tsz; j++)
        {
            for(int z = 0; z < K; z++)
            {
                if(i & (1 << z)) continue;
                int nstate = go(j, z);
                int add = calc(nstate);
                int nmask = i | (1 << z);
                if(dp[nmask][nstate] < dp[i][j] + add)
                {
                    dp[nmask][nstate] = dp[i][j] + add;
                    pdp[nmask][nstate] = {z, j};
                }
            }
        }
    string ans = "";
    int curmask = (1 << K) - 1;
    int curstate = max_element(dp[curmask].begin(), dp[curmask].end()) - dp[curmask].begin();
    while(curmask != 0)
    {
        int cc = pdp[curmask][curstate].first;
        int ns = pdp[curmask][curstate].second;
        ans.push_back(char('a' + cc));
        curmask ^= (1 << cc);
        curstate = ns;
    }
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    cout << max_element(a.begin(), a.end()) - a.begin() + 1 << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    for (int i = n & 1; i < n - 2; i += 2) swap(p[i], p[i + 1]);
    for (int &x : p) cout << x << ' ';
    cout << '\n';
  }
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n;
		scanf("%d", &n);
		vector<int> a(n), b(n);
		forn(i, n) scanf("%d", &a[i]);
		forn(i, n) scanf("%d", &b[i]);
		priority_queue<int> qa(a.begin(), a.end());
		priority_queue<int> qb(b.begin(), b.end());
		int ans = 0;
		while (!qa.empty()){
			if (qa.top() == qb.top()){
				qa.pop();
				qb.pop();
				continue;
			}
			++ans;
			if (qa.top() > qb.top()){
				qa.push(to_string(qa.top()).size());
				qa.pop();
			}
			else{
				qb.push(to_string(qb.top()).size());
				qb.pop();
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int comp(char c, char d){
	return c < d ? -1 : (c > d ? 1 : 0);
}

int main() {
	int t;
	cin >> t;
	forn(_, t){
		string s;
		cin >> s;
		int n = s.size();
		vector<vector<int>> dp(n + 1, vector<int>(n + 1));
		for (int len = 2; len <= n; len += 2) forn(l, n - len + 1){
			int r = l + len;
			dp[l][r] = 1;
			{
				int res = -1;
				if (dp[l + 1][r - 1] != 0)
					res = max(res, dp[l + 1][r - 1]);
				else
					res = max(res, comp(s[l], s[r - 1]));
				if (dp[l + 2][r] != 0)
					res = max(res, dp[l + 2][r]);
				else
					res = max(res, comp(s[l], s[l + 1]));
				dp[l][r] = min(dp[l][r], res);
			}
			{
				int res = -1;
				if (dp[l + 1][r - 1] != 0)
					res = max(res, dp[l + 1][r - 1]);
				else
					res = max(res, comp(s[r - 1], s[l]));
				if (dp[l][r - 2] != 0)
					res = max(res, dp[l][r - 2]);
				else
					res = max(res, comp(s[r - 1], s[r - 2]));
				dp[l][r] = min(dp[l][r], res);
			}
		}
		if (dp[0][n] == -1)
			cout << "Alice\n";
		else if (dp[0][n] == 0)
			cout << "Draw\n";
		else
			cout << "Bob\n";
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

long long gcd(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long x1, y1;
	long long d = gcd(b, a % b, x1, y1);
	x = y1;
	y = x1 - y1 * (a / b);
	return d;
}

bool find_any_solution(long long a, long long b, long long c, long long &x0, long long &y0, long long &g) {
	g = gcd(abs(a), abs(b), x0, y0);
	if (c % g) {
		return false;
	}
	x0 *= c / g;
	y0 *= c / g;
	if (a < 0) x0 = -x0;
	if (b < 0) y0 = -y0;
	return true;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n), b(n);
	forn(i, n) scanf("%d%d", &a[i], &b[i]);
	long long cur = accumulate(b.begin(), b.end(), 0ll);
	vector<int> difs(n);
	forn(i, n) difs[i] = a[i] - b[i];
	sort(difs.begin(), difs.end(), greater<int>());
	vector<long long> bst(n + 1);
	forn(i, n + 1){
		bst[i] = cur;
		if (i < n)
			cur += difs[i];
	}
	int mx = max_element(bst.begin(), bst.end()) - bst.begin();
	int m;
	scanf("%d", &m);
	forn(_, m){
		int x, y;
		scanf("%d%d", &x, &y);
		long long x0, y0, g;
		if (!find_any_solution(x, y, n, x0, y0, g)){
			puts("-1");
			continue;
		}
		long long l = x * 1ll * y / g;
		long long red = x0 * 1ll * x;
		red = red + (max(0ll, mx - red) + l - 1) / l * l;
		red = red - max(0ll, red - mx) / l * l;
		long long ans = -1;
		if (red <= n) ans = max(ans, bst[red]);
		red -= l;
		if (red >= 0) ans = max(ans, bst[red]);
		printf("%lld\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>     

using namespace std;

const int N = 1003;

int n;
int a[N];
vector<int> g[N * N];
int mt[N];
bool used[N * N];
vector<int> val;

bool kuhn(int x)
{
    if(used[x]) return false;
    used[x] = true;
    for(auto y : g[x])
        if(mt[y] == -1 || kuhn(mt[y]))
        {
            mt[y] = x;
            return true;
        }
    return false;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++)
        for(int j = 1; j <= n; j++)
            val.push_back(a[i] * j);
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    int v = val.size();
    long long ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 1; j <= n; j++)
        {
            int k = lower_bound(val.begin(), val.end(), a[i] * j) - val.begin();
            g[k].push_back(i);
        }
    for(int i = 0; i < n; i++) mt[i] = -1;
    for(int i = 0; i < v; i++)
    {
        if(kuhn(i))
        {
            ans += val[i];
            for(int j = 0; j < v; j++) used[j] = false;
        }
    }
    cout << ans << endl;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int MOD = 998244353;

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
	return a;
}

int mul(int a, int b){
	return a * 1ll * b % MOD;
}

int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int main() {
	int D, n, m;
	
	scanf("%d%d%d", &D, &n, &m);
	
	vector<int> inv(D + 1);
	forn(i, D + 1) inv[i] = binpow(i, MOD - 2);
	
	vector<int> b(n);
	forn(i, n) scanf("%d", &b[i]);
	
	vector<int> a(m);
	forn(i, m) scanf("%d", &a[i]);
	sort(a.begin(), a.end());
	
	int fl = (1 << m) - 1;
	vector<int> ways(1 << m, 1);
	forn(i, m) forn(j, n){
		int d = abs(b[j] - a[i]);
		int mask;
		if (b[j] > a[i]){
			int r = lower_bound(a.begin(), a.end(), b[j] + d) - a.begin();
			mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
		}
		else{
			int l = lower_bound(a.begin(), a.end(), b[j] - d) - a.begin();
			mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
		}
		ways[mask] = mul(ways[mask], d);
		mask ^= (1 << i);
		ways[mask] = mul(ways[mask], inv[d]);
	}
	
	forn(i, m) for (int mask = fl; mask >= 0; --mask) if ((mask >> i) & 1){
		ways[mask ^ (1 << i)] = mul(ways[mask ^ (1 << i)], ways[mask]);
	}
	
	ways[0] = binpow(D + 1, n);
	forn(mask, 1 << m){
		ways[mask] = mul(ways[mask], __builtin_popcount(mask) & 1 ? MOD - 1 : 1);
	}
	forn(i, m) forn(mask, 1 << m) if (!((mask >> i) & 1)){
		ways[mask ^ (1 << i)] = add(ways[mask ^ (1 << i)], ways[mask]);
	}
	
	int q;
	scanf("%d", &q);
	forn(_, q){
		int x;
		scanf("%d", &x);
		int ans = binpow(D + 1, n + 1);
		forn(i, m){
			int d = abs(x - a[i]);
			int mask;
			if (x > a[i]){
				int r = lower_bound(a.begin(), a.end(), x + d) - a.begin();
				mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
			}
			else{
				int l = lower_bound(a.begin(), a.end(), x - d) - a.begin();
				mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
			}
			ans = add(ans, mul(add(ways[mask], -ways[mask ^ (1 << i)]), d));
		}
		printf("%d\n", ans);
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        string s1, s2;
        cin >> s1 >> s2;
        s1 += s2;
        cout << set<char>(s1.begin(), s1.end()).size() - 1 << endl;
    }
}

for _ in range(int(input())):
	n, m, sx, sy, d = map(int, input().split())
	if min(sx - 1, m - sy) <= d and min(n - sx, sy - 1) <= d:
	    print(-1)
	else:
	    print(n + m - 2)

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(' ').map { it.toInt() }
        val b = readLine()!!.split(' ').map { it.toInt() }

        val indices = (0 until n).sortedBy { a[it] }
        val mn = Array(n) { 0 }
        val mx = Array(n) { 0 }

        var lst = n
        for (i in n - 1 downTo 0) {
            val pos = indices[i]
            mn[pos] = lowerBound(b, a[pos])
            mx[pos] = lst - 1;
            if (i == mn[pos])
                lst = i

            mn[pos] = b[mn[pos]] - a[pos]
            mx[pos] = b[mx[pos]] - a[pos]
        }
        println(mn.joinToString(" "))
        println(mx.joinToString(" "))
    }
}

fun lowerBound(a: List<Int>, v: Int): Int {
    var l = -1; var r = a.size
    while (r - l > 1) {
        val m = (l + r) / 2
        if (a[m] < v)
            l = m
        else
            r = m
    }
    return r
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int& x : a) cin >> x;
    for (int& x : b) cin >> x;
    
    auto check = [&](int ans) {
      map<int, int> cnt;
      for (int x : a) ++cnt[x & ans];
      for (int x : b) --cnt[~x & ans];
      bool ok = true;
      for (auto it : cnt) ok &= it.second == 0;
      return ok;
    };
    
    int ans = 0;
    for (int bit = 29; bit >= 0; --bit) 
      if (check(ans | (1 << bit)))
        ans |= 1 << bit;
    
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int AL = 26;

vector<int> prefix_function(const string &s){
	int n = s.size();
	vector<int> p(n);
	for (int i = 1; i < n; ++i){
		int k = p[i - 1];
		while (k > 0 && s[i] != s[k])
			k = p[k - 1];
		k += (s[i] == s[k]);
		p[i] = k;
	}
	return p;
}

int main() {
	cin.tie(0);
	iostream::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size();
	auto p = prefix_function(s);
	vector<vector<int>> A(n, vector<int>(AL));
	forn(i, n) forn(j, AL){
		if (i > 0 && j != s[i] - 'a')
			A[i][j] = A[p[i - 1]][j];
		else
			A[i][j] = i + (j == s[i] - 'a');
	}
	int q;
	cin >> q;
	vector<vector<int>> ans(q);
	forn(z, q){
		string t;
		cin >> t;
		int m = t.size();
		s += t;
		for (int i = n; i < n + m; ++i){
		    A.push_back(vector<int>(AL));
			forn(j, AL){
				if (j != s[i] - 'a')
					A[i][j] = A[p[i - 1]][j];
				else
					A[i][j] = i + (j == s[i] - 'a');
			}
			p.push_back(A[p[i - 1]][s[i] - 'a']);
			ans[z].push_back(p[i]);
		}
		forn(_, m){
			p.pop_back();
			s.pop_back();
			A.pop_back();
		}
	}
	for (auto &it : ans){
		for (int x : it)
			cout << x << ' ';
		cout << '\n';
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 400043;
const int INF = int(1e9);

struct edge
{
    int y, c, f;
    edge() {};
    edge(int y, int c, int f) : y(y), c(c), f(f) {};
};

vector<edge> e;
vector<int> g[N];
int S, T, V;
int d[N], lst[N];
int n1, n2, m, q;
map<pair<int, int>, int> es;

void add_edge(int x, int y, int c)
{
    g[x].push_back(e.size());
    e.push_back(edge(y, c, 0));
    g[y].push_back(e.size());
    e.push_back(edge(x, 0, 0));
}

int rem(int x)
{
    return e[x].c - e[x].f;
}

bool bfs()
{
    for (int i = 0; i < V; i++)
        d[i] = INF;
    d[S] = 0;
    queue<int> q;
    q.push(S);
    while (!q.empty())
    {
        int k = q.front();
        q.pop();
        for (auto y : g[k])
        {
            if (rem(y) == 0)
                continue;
            int to = e[y].y;
            if (d[to] > d[k] + 1)
            {
                q.push(to);
                d[to] = d[k] + 1;
            }
        }
    }
    return d[T] < INF;
}

int dfs(int x, int mx)
{
    if (x == T || mx == 0)
        return mx;
    int sum = 0;
    for (; lst[x] < g[x].size(); lst[x]++)
    {
        int num = g[x][lst[x]];
        int r = rem(num);
        if (r == 0)
            continue;
        int to = e[num].y;
        if (d[to] != d[x] + 1)
            continue;
        int pushed = dfs(to, min(r, mx));
        if (pushed > 0)
        {
            e[num].f += pushed;
            e[num ^ 1].f -= pushed;
            sum += pushed;
            mx -= pushed;
            if (mx == 0)
                return sum;
        }
    }
    return sum;
}

int Dinic()
{
    int ans = 0;
    while (bfs())
    {
        for (int i = 0; i < V; i++)
            lst[i] = 0;
        int f = 0;
        do
        {
            f = dfs(S, INF);
            ans += f;
        } while (f > 0);
    }
    return ans;
}

int main()
{
    scanf("%d %d %d %d", &n1, &n2, &m, &q);
    S = n1 + n2;
    T = S + 1;
    V = T + 1;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        es[make_pair(x, y)] = i + 1;
        add_edge(x, n1 + y, 1);
    }
    for (int i = 0; i < n1; i++)
        add_edge(S, i, 1);
    for (int i = 0; i < n2; i++)
        add_edge(i + n1, T, 1);
    Dinic();
    bfs();
    vector<int> vertex_cover;
    map<int, int> index;
    set<int> matched;
    long long sum = 0;
    for (int i = 0; i < n1; i++)
        if (d[i] == INF)
        {
            vertex_cover.push_back(i + 1);
            for (auto ei : g[i])
                if (e[ei].f == 1)
                {
                    int idx = es[make_pair(i, e[ei].y - n1)];
                    index[i + 1] = idx;
                    sum += idx;
                    matched.insert(idx);
                }
        }
    for (int i = 0; i < n2; i++)
        if (d[i + n1] != INF)
        {
            vertex_cover.push_back(-(i + 1));
            for (auto ei : g[i + n1])
                if (e[ei].f == -1)
                {
                    int idx = es[make_pair(e[ei].y, i)];
                    index[-(i + 1)] = idx;
                    sum += idx;    
                    matched.insert(idx);
                }
        }
    for (int i = 0; i < q; i++)
    {
        int s;
        scanf("%d", &s);
        if (s == 1)
        {
            puts("1");
            int v = vertex_cover.back();
            vertex_cover.pop_back();
            printf("%d\n", v);
            sum -= index[v];
            matched.erase(index[v]);
            printf("%lld\n", sum);
        }
        else
        {
            printf("%d\n", (int)matched.size());
            for(auto x : matched) printf("%d ", x);
            puts("");
        }   
        fflush(stdout);
    }
}

for _ in range(int(input())):
    n = int(input())
    print(1 + (n == 1) if n <= 3 else (n + 2) // 3)

for _ in range(int(input())):
	n = int(input())
	p = [i + 1 for i in range(n)]
	print(n)
	for i in range(n):
		print(*p)
		if i < n - 1:
			p[i], p[i + 1] = p[i + 1], p[i]

INF = 2 * 10**9

for _ in range(int(input())):
	m = int(input())
	a = [[int(x) for x in input().split()] for i in range(2)]
	su = [[-INF for j in range(m + 1)] for i in range(2)]
	for i in range(2):
		for j in range(m - 1, -1, -1):
			su[i][j] = max(su[i][j + 1] - 1, a[i][j], a[i ^ 1][j] - (2 * (m - j) - 1))
	pr = a[0][0] - 1
	ans = INF
	for j in range(m):
		jj = j & 1
		ans = min(ans, max(pr, su[jj][j + 1] - 2 * j - 1, a[jj ^ 1][j] - 2 * m + 1))
		pr = max(pr, a[jj ^ 1][j] - 2 * j - 1)
		ans = min(ans, max(pr, su[jj ^ 1][j + 1] - 2 * j - 2))
		if j < m - 1:
			pr = max(pr, a[jj ^ 1][j + 1] - 2 * j - 2)
	print(ans + 2 * m)

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> dp(n + 1), ans(n + 1);
  dp[0] = 1;
  for (int mn = 0; mn + k <= n; mn += k++) {
    vector<int> sum(k);
    for (int i = mn; i <= n; ++i) {
      int cur = dp[i];
      dp[i] = sum[i % k];
      (sum[i % k] += cur) %= MOD;
      (ans[i] += dp[i]) %= MOD;
    }
  }
  for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}

#include<bits/stdc++.h>

using namespace std;     
const int K = 18;

struct node
{
    long long sum, pref, suff, ans;
    
    node(const node& l, const node& r)
    {                                                                                          
        sum = l.sum + r.sum;
        pref = max(l.pref, l.sum + r.pref);
        suff = max(r.suff, r.sum + l.suff);
        ans = max(max(l.ans, r.ans), l.suff + r.pref);
    }

    node(int x)
    {
        sum = x;
        pref = suff = ans = max(x, 0);
    }

    node() {};
};

int a[1 << K];
vector<node> tree[2 << K];  

void build(int v, int l, int r)
{
    tree[v].resize(r - l);
    if(l == r - 1)
    {
        tree[v][0] = node(a[l]);  
    }
    else
    {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
        for(int i = 0; i < m - l; i++)
        {
            tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);
            tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]);    
        }
    }
}

int main()
{            
    int n;
    scanf("%d", &n);
    int m = (1 << n);
    for(int i = 0; i < m; i++)
    {
        scanf("%d", &a[i]);
    }
    build(0, 0, m);
    int q;
    scanf("%d", &q);
    int cur = 0;
    for(int i = 0; i < q; i++)
    {
        int x;
        scanf("%d", &x);
        cur ^= (1 << x);
        printf("%lld\n", tree[0][cur].ans);
    }
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;   
const int N = 2043;

int dp[N][N];

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}   

int sub(int x, int y)
{
    return add(x, -y);
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

void precalc()
{
    dp[1][1] = 1;
    for(int i = 1; i < N - 1; i++)
        for(int j = 1; j <= i; j++)
        {
            dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j));
            dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
        }
}

int solve(int n, int m, int k)
{
    int way1 = (m / 2) + (m % 2);
    int curA = n;
    int ans = 0;
    int ways_chosen = way1;
    int ways_other = binpow(m, n - 1);
    int invm = inv(m);
    for(int i = 1; i <= k; i++)
    {
        ans = add(ans, mul(mul(curA, dp[k][i]), mul(ways_chosen, ways_other)));
        curA = mul(curA, sub(n, i));
        ways_chosen = mul(way1, ways_chosen);
        ways_other = mul(ways_other, invm);
    }  
    return ans;
}   

int main()
{
    int t;
    cin >> t;
    precalc();
    for(int i = 0; i < t; i++)
    {
        int n, m, k;
        cin >> n >> m >> k;
        cout << solve(n, m, k) << endl;
    }
}

for _ in range(int(input())):
	x = int(input())
	a = [0] + [int(x) for x in input().split()]
	print("YES" if a[x] != 0 and a[a[x]] != 0 else "NO")

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [0] + [max(0, a[i] - a[i + 1]) for i in range(n - 1)]
r = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)]
for i in range(n - 1):
    l[i + 1] += l[i]
    r[i + 1] += r[i]
for _ in range(m):
    s, t = map(int, input().split())
    if s < t:
        print(l[t - 1] - l[s - 1])
    else:
        print(r[s - 1] - r[t - 1])

#include <bits/stdc++.h>

using namespace std;

int main() {
  auto check = [](const string& s) {
    int bal = 0;
    for (char c : s) {
      if (c == '(') ++bal;
      if (c == ')') --bal;
      if (bal < 0) return false;
    }
    return bal == 0;
  };
  
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    vector<int> pos;
    int op = s.size() / 2, cl = s.size() / 2;
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == '?') pos.push_back(i);
      if (s[i] == '(') --op;
      if (s[i] == ')') --cl;
    }
    for (int i = 0; i < pos.size(); ++i) {
      if (i < op) s[pos[i]] = '(';
      else s[pos[i]] = ')';
    }
    bool ok = true;
    if (op > 0 && cl > 0) {
      swap(s[pos[op - 1]], s[pos[op]]);
      if (check(s)) ok = false;
    }
    cout << (ok ? "YES\n" : "NO\n");
  }
} 

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> a(m);
	forn(i, m) scanf("%d", &a[i]);
	
	int l = 0;
	while ((1 << l) <= m) ++l;
	vector<vector<int>> st(l, vector<int>(m));
	forn(i, m) st[0][i] = a[i];
	for (int j = 1; j < l; ++j) forn(i, m){
		st[j][i] = st[j - 1][i];
		if (i + (1 << (j - 1)) < m)
			st[j][i] = max(st[j][i], st[j - 1][i + (1 << (j - 1))]);
	}
	vector<int> pw(m + 1, 0);
	for (int i = 2; i <= m; ++i) pw[i] = pw[i / 2] + 1;
	auto get = [&](int l, int r){
		if (l > r) swap(l, r);
		++r;
		int len = pw[r - l];
		return max(st[len][l], st[len][r - (1 << len)]);
	};
	
	int q;
	scanf("%d", &q);
	forn(_, q){
		int xs, ys, xf, yf, k;
		scanf("%d%d%d%d%d", &xs, &ys, &xf, &yf, &k);
		--xs, --ys, --xf, --yf;
		if (ys % k != yf % k || xs % k != xf % k){
			puts("NO");
			continue;
		}
		int mx = (n - xs - 1) / k * k + xs;
		puts(get(ys, yf) <= mx ? "YES" : "NO");
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 13;

int n;
int a[N], b[N];
vector<int> g[N];
set<int> vals[N];

void init(int v, int p) {
  b[v] = a[v];
  if (p != -1) b[v] ^= b[p];
  for (int u : g[v]) if (u != p)
    init(u, v);
}

int ans;

void calc(int v, int p) {
  bool bad = false;
  vals[v].insert(b[v]);
  for (int u : g[v]) if (u != p) {
    calc(u, v);
    if (vals[v].size() < vals[u].size()) vals[v].swap(vals[u]);
    for (int x : vals[u]) bad |= vals[v].count(x ^ a[v]);
    for (int x : vals[u]) vals[v].insert(x);
    vals[u].clear();
  }
  if (bad) {
    ans += 1;
    vals[v].clear();
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  init(0, -1);
  calc(0, -1);
  cout << ans << '\n';
} 

for _ in range(int(input())):
    a = [list(map(int, input().split())) for i in range(2)]
    cnt = sum([sum(a[i]) for i in range(2)])
    if cnt == 0:
        print(0)
    elif cnt == 4:
        print(2)
    else:
        print(1)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    cout << 2 << '\n';
    for (int i = 1; i <= n; ++i) if (i % 2 != 0)
      for (int j = i; j <= n; j *= 2)
        cout << j << ' ';
    cout << '\n';
  }
} 

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n, m;
		scanf("%d%d", &n, &m);
		vector<int> a(m);
		forn(i, m){
			scanf("%d", &a[i]);
			--a[i];
		}
		vector<int> cnt(n);
		forn(i, m) ++cnt[a[i]];
		auto check = [&](int t){
			long long fr = 0, need = 0;
			forn(i, n){
				if (t >= cnt[i])
					fr += (t - cnt[i]) / 2;
				else
					need += cnt[i] - t;
			}
			return need <= fr;
		};
		int l = 0, r = 2 * m;
		int res = -1;
		while (l <= r){
			int m = (l + r) / 2;
			if (check(m)){
				res = m;
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		printf("%d\n", res);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int& x : b) cin >> x;
    vector<pair<int, int>> ev(n);
    for (int i = 0; i < n; ++i)
      ev[i] = {(i + 1) / (b[i] + 1) + 1, i};
    sort(ev.begin(), ev.end());
    set<pair<int, int>> s;
    int j = 0;
    for (int i = 1; i <= n; ++i) {
      while (j < n && ev[j].first == i) {
        int id = ev[j++].second;
        s.insert({b[id] ? (id + 1) / b[id] : n, id});
      }
      a[s.begin()->second] = i;
      s.erase(s.begin());
    }
    for (int& x : a) cout << x << ' ';
    cout << '\n';
  }
} 

#include <bits/stdc++.h>

using namespace std;

vector<int> zf(const string &s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        string s, t;
        cin >> n >> m >> s >> t;
        
        int ans = 1e9;
        
        bool bad = false;
        vector<int> lpos(m), rpos(m);
        for (int i = 0; i < m; ++i) {
            if (i > 0) {
                lpos[i] = lpos[i - 1] + 1;
            } else {
                lpos[i] = 0;
            }
            while (lpos[i] < n && s[lpos[i]] != t[i]) {
                ++lpos[i];
            }
            if (lpos[i] >= n) {
                bad = true;
                break;
            }
        }
        for (int i = m - 1; i >= 0; --i) {
            if (i + 1 < m) {
                rpos[i] = rpos[i + 1] - 1;
            } else {
                rpos[i] = n - 1;
            }
            while (rpos[i] >= 0 && s[rpos[i]] != t[i]) {
                --rpos[i];
            }
            if (rpos[i] < 0) {
                bad = true;
                break;
            }
        }
        if (bad) {
            cout << -1 << endl;
            continue;
        }
        
        for (int pos = 0; pos <= n; ++pos) {
            string tmp = s.substr(0, pos);
            reverse(tmp.begin(), tmp.end());
            tmp += "#" + t;
            reverse(tmp.begin() + pos + 1, tmp.end());
            vector<int> z = zf(tmp);
            for (int suf = 0; suf <= m; ++suf) {
                if (pos - suf < 0) {
                    continue;
                }
                if (suf < m && rpos[suf] < pos) {
                    continue;
                }
                if (suf - 1 >= 0 && lpos[suf - 1] > pos) {
                    continue;
                }
                int rg = 0;
                if (suf != 0) {
                    int sum = (pos - z[pos + 1 + m - suf]) + (pos - suf);
                    rg = (sum != 0) + sum;
                } else {
                    rg = pos;
                }
                ans = min(ans, (n - pos) + rg);
            }
        }
        cout << ans << endl;
    }
    
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int M = 200001;

typedef array<long long, 3> vec;
typedef array<vec, 3> mat;

vec operator+(const vec& a, const vec& b)
{
    vec c;
    for(int i = 0; i < 3; i++) c[i] = a[i] + b[i];
    return c;
}

vec operator-(const vec& a, const vec& b)
{
    vec c;
    for(int i = 0; i < 3; i++) c[i] = a[i] - b[i];
    return c;
}

vec operator*(const mat& a, const vec& b)
{
    vec c;
    for(int i = 0; i < 3; i++) c[i] = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            c[i] += a[i][j] * b[j];
    return c;
}

mat operator*(const mat& a, const mat& b)
{
    mat c;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            c[i][j] = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                c[i][k] += a[i][j] * b[j][k];
    return c;
}

mat F = {vec({1, 0, 0}), vec({1, 1, 0}), vec({1, 2, 1})};
mat B = {vec({1, 0, 0}), vec({-1, 1, 0}), vec({1, -2, 1})};
mat E = {vec({1, 0, 0}), vec({0, 1, 0}), vec({0, 0, 1})};

vec S = {1, 0, 0};
vec Z = {0, 0, 0};

vec t[4 * N];
mat f[4 * N];
bool active[4 * N];
bool has[N];
int d, q;

vec getVal(int v)
{
    if(!active[v]) return Z;
    return f[v] * t[v];
}

void recalc(int v)
{
    t[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2);    
}

void build(int v, int l, int r)
{
    if(l == r - 1)
    {
        f[v] = E;
        t[v] = S;
        active[v] = false;                 
    }
    else
    {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
        f[v] = E;
        recalc(v);
        active[v] = true;               
    }
}

void push(int v)
{
    if(f[v] == E) return;
    t[v] = f[v] * t[v];
    f[v * 2 + 1] = f[v] * f[v * 2 + 1];
    f[v * 2 + 2] = f[v] * f[v * 2 + 2];
    f[v] = E;
}

void updSegment(int v, int l, int r, int L, int R, bool adv)
{
    if(L >= R) return;
    if(l == L && r == R)
    {
        if(adv) f[v] = F * f[v];
        else f[v] = B * f[v];
        return;
    }
    push(v);
    int m = (l + r) / 2;
    updSegment(v * 2 + 1, l, m, L, min(m, R), adv);
    updSegment(v * 2 + 2, m, r, max(m, L), R, adv);
    recalc(v);
}

void setState(int v, int l, int r, int pos, bool val)
{
    if(l == r - 1)
    {   
        active[v] = val;
        return;
    }
    push(v);
    int m = (l + r) / 2;
    if(pos < m)
        setState(v * 2 + 1, l, m, pos, val);
    else
        setState(v * 2 + 2, m, r, pos, val);
    recalc(v);
}

void addPoint(int x)
{
    int lf = max(0, x - d);
    int rg = x;
    if(lf < rg)
        updSegment(0, 0, M, lf, rg, true);
    setState(0, 0, M, x, true);        
}

void delPoint(int x)
{
    int lf = max(0, x - d);
    int rg = x;
    if(lf < rg)
        updSegment(0, 0, M, lf, rg, false);
    setState(0, 0, M, x, false);        
}

void query(int x)
{
    if(has[x])
    {
        has[x] = false;
        delPoint(x);
    }
    else
    {
        has[x] = true;
        addPoint(x);
    }
    vec res = getVal(0);
    printf("%lld\n", (res[2] - res[1]) / 2);
}

int main()
{
    scanf("%d %d", &q, &d);
    build(0, 0, M);
    for(int i = 0; i < q; i++)
    {
        int x;
        scanf("%d", &x);
        query(x);
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", H"r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n, m;
        cin >> n >> m;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            sum += x;
        }
        cout << max(0, sum - m) << endl;
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<long long> p(n), s(n + 1);
  for (auto& x : p) cin >> x;
  sort(p.begin(), p.end());
  for (int i = 0; i < n; ++i) s[i + 1] = s[i] + p[i];
  while (q--) {
    int x, y;
    cin >> x >> y;
    cout << s[n - x + y] - s[n - x] << '\n';
  }
} 

for _ in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	if s.count('b') != t.count('b'):
		print("NO")
		continue
	j = 0
	for i in range(n):
		if s[i] == 'b':
			continue
		while t[j] == 'b':
			j += 1
		if s[i] != t[j] or (s[i] == 'a' and i > j) or (s[i] == 'c' and i < j):
			print("NO")
			break
		j += 1
	else:
		print("YES")

#include<bits/stdc++.h>

using namespace std;

char ask_character(int i)
{
    cout << "? 1 " << i << endl;
    cout.flush();
    string s;
    cin >> s;
    return s[0];
}

int ask_cnt(int l, int r)
{
    cout << "? 2 " << l << " " << r << endl;
    cout.flush();
    int x;
    cin >> x;
    return x;
}

int main()
{
    int n;
    cin >> n;
    string s = "";
    vector<vector<int>> cnt(n + 1);
    for(int i = 0; i < n; i++)
    {
        if(i == 0)
        {
            s.push_back(ask_character(1));
            cnt[0] = {1};
        }
        else
        {
             int cur = ask_cnt(1, i + 1);
             if(cur > cnt[i - 1][0])
                s.push_back(ask_character(i + 1));
             else
             {
                map<char, int> last;
                for(int j = 0; j < s.size(); j++)
                    last[s[j]] = j;
                vector<int> lasts;
                for(auto x : last) lasts.push_back(x.second);
                sort(lasts.begin(), lasts.end());
                int l = 0;
                int r = lasts.size();
                // there is always an occurrence in [lasts[l], i)
                // there is no occurrence in [lasts[r], i)
                while(r - l > 1)
                {
                    int m = (l + r) / 2;
                    int c = ask_cnt(lasts[m] + 1, i + 1);
                    if (c == cnt[i - 1][lasts[m]])
                        l = m;
                    else
                        r = m;
                }   
                s.push_back(s[lasts[l]]);                                                
             }
             cnt[i].resize(i + 1);
             set<char> q;
             for(int j = i; j >= 0; j--)
             {
                q.insert(s[j]);
                cnt[i][j] = q.size();
             }
        }
    }
    cout << "! " << s << endl;
    cout.flush();
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 143;
const int K = 5;
const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;   
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int fact[N];
int rfact[N];

int A(int n, int k)
{
    return mul(fact[n], rfact[n - k]);
}

int n;

vector<int> g[N];
int x[N];
int y[N];
int dist[N][N];
int color[N];
int dp[N][N];

int cc = 0;
set<int> pts;
vector<int> compsize;

void dfs1(int i)
{
    //cerr << i << endl;
    if(pts.count(i) == 1) return;
    pts.insert(i);
    for(auto v : g[i])
    {
        dfs1(v);
    }
}

void dfs2(int i, int c)
{
    if(color[i] == c) return;
    color[i] = c;
    for(auto v : g[i])
        dfs2(v, c);
}

int main()
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(i, fact[i - 1]);
    for(int i = 0; i < N; i++)
        rfact[i] = binpow(fact[i], MOD - 2);


    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d %d", &x[i], &y[i]);    
    }
    for(int i = 0; i < n; i++)
    {
        dist[i][i] = int(1e9);
        for(int j = 0; j < n; j++)
            if(i != j)
                dist[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
    }
    for(int i = 0; i < n; i++)
    {
        int d = *min_element(dist[i], dist[i] + n);
        for(int j = 0; j < n; j++)
            if(dist[i][j] == d) g[i].push_back(j);    
    }

    for(int i = 0; i < n; i++)
    {
        if(color[i] != 0) continue;
        cc++;
        pts.clear();
        dfs1(i);
        //cerr << "!" << endl; 
        int d = *min_element(dist[i], dist[i] + n);                      
        set<int> pts2 = pts;
        bool bad = false;
        for(auto x : pts)
            for(auto y : pts2)
                if(x != y && dist[x][y] != d)
                    bad = true;
        if(bad)           
        {
            color[i] = cc;
            compsize.push_back(1);
        }
        else
        {
            dfs2(i, cc);
            compsize.push_back(pts.size());
        }
    }            

    dp[0][0] = 1;
    int m = compsize.size();
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
        {
            if(dp[i][j] == 0) continue;
            dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
            if(compsize[i] != 1)
            {
                dp[i + 1][j + compsize[i]] = add(dp[i + 1][j + compsize[i]], dp[i][j]);
            }
        }
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = add(ans, mul(dp[m][i], A(n, i)));
    cout << ans << endl;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct constraint{
	int tp, i, j, x;
};

vector<vector<int>> g, tg;
vector<char> used;
vector<int> clr, ord;

void ts(int v){
	used[v] = true;
	for (int u : g[v]) if (!used[u])
		ts(u);
	ord.push_back(v);
}

void dfs(int v, int k){
	clr[v] = k;
	for (int u : tg[v]) if (clr[u] == -1)
		dfs(u, k);
}

void either(int x, int y){
	g[x ^ 1].push_back(y);
	g[y ^ 1].push_back(x);
	tg[y].push_back(x ^ 1);
	tg[x].push_back(y ^ 1);
}

void implies(int x, int y){
	either(x ^ 1, y);
}

void must(int x){
	either(x, x);
}

int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n, m, k;
		scanf("%d%d%d", &n, &m, &k);
		vector<constraint> c(m);
		forn(i, m){
			scanf("%d%d", &c[i].tp, &c[i].i);
			if (c[i].tp != 1) scanf("%d", &c[i].j);
			scanf("%d", &c[i].x);
			--c[i].i, --c[i].j;
		}
		int vts = n * (k + 2);
		g.assign(2 * vts, vector<int>());
		tg.assign(2 * vts, vector<int>());
		forn(i, n){
			forn(j, (k + 2) - 1)
				implies(2 * (i * (k + 2) + j + 1) + 1, 2 * (i * (k + 2) + j) + 1);
			must(2 * (i * (k + 2) + 1) + 1);
			must(2 * (i * (k + 2) + k + 1));
		}
		forn(i, n - 1) forn(j, k + 2){
			implies(2 * (i * (k + 2) + j) + 1, 2 * ((i + 1) * (k + 2) + j) + 1);
		}
		forn(i, m){
			if (c[i].tp == 1)
				either(2 * (c[i].i * (k + 2) + c[i].x + 1) + 1, 2 * (c[i].i * (k + 2) + c[i].x));
			else if (c[i].tp == 2){
				for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); ++a){
					implies(2 * (c[i].i * (k + 2) + a) + 1, 2 * (c[i].j * (k + 2) + (c[i].x - a) + 1));
					implies(2 * (c[i].j * (k + 2) + a) + 1, 2 * (c[i].i * (k + 2) + (c[i].x - a) + 1));
				}
			}
			else{
				for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); ++a){
					implies(2 * (c[i].i * (k + 2) + a + 1), 2 * (c[i].j * (k + 2) + (c[i].x - a)) + 1);
					implies(2 * (c[i].j * (k + 2) + a + 1), 2 * (c[i].i * (k + 2) + (c[i].x - a)) + 1);
				}
			}
		}
		used.assign(2 * vts, 0);
		ord.clear();
		forn(i, used.size()) if (!used[i]) ts(i);
		reverse(ord.begin(), ord.end());
		clr.assign(2 * vts, -1);
		int cc = 0;
		for (int v : ord) if (clr[v] == -1){
			dfs(v, cc);
			++cc;
		}
		vector<int> vals(vts);
		bool ans = true;
		forn(i, vts){
			if (clr[2 * i] == clr[2 * i + 1]){
				ans = false;
				break;
			}
			vals[i] = (clr[2 * i] < clr[2 * i + 1]);
		}
		if (!ans){
			puts("-1");
			continue;
		}
		forn(i, n){
			int lst = 0;
			forn(j, k + 2) if (vals[i * (k + 2) + j])
				lst = j;
			printf("%d ", lst);
		}
		puts("");
	}
	return 0;
}

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    b = list(map(int, input().split()))
    
    print('Alice' if max(a) >= max(b) else 'Bob')
    print('Alice' if max(a) > max(b) else 'Bob')

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	print(a[sum(map(int, input().split())) % n])

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	tmp = [i for i in range(n)]
	tmp.sort(key=lambda i: [a[i], b[i]])
	for i in range(n - 1):
		if a[tmp[i]] > a[tmp[i + 1]] or b[tmp[i]] > b[tmp[i + 1]]:
			print("-1")
			break
	else:
		ans = []
		for i in range(n - 1):
			for j in range(n - 1):
				if a[j] > a[j + 1] or b[j] > b[j + 1]:
					a[j], a[j + 1] = a[j + 1], a[j]
					b[j], b[j + 1] = b[j + 1], b[j]
					ans.append([j + 1, j + 2])
		print(len(ans))
		for it in ans:
			print(*it)

#include<bits/stdc++.h>

using namespace std;

int main()
{   
    int n;
    cin >> n;
    long long v;
    cin >> v;
    queue<long long> q;
    map<long long, int> dist;
    dist[v] = 0;
    q.push(v);
    while(!q.empty())
    {
        long long k = q.front();
        q.pop();
        string s = to_string(k);
        if(s.size() == n)
        {
            cout << dist[k] << endl;
            return 0;
        }
        for(auto x : s)
        {
            if(x == '0') continue;
            long long w = k * int(x - '0');
            if(!dist.count(w))
            {
                dist[w] = dist[k] + 1;
                q.push(w);
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const long long INF64 = 1e18;

typedef pair<int, int> pt;
#define x first
#define y second

int main() {
	int n;
	scanf("%d", &n);
	vector<vector<pt>> d(n - 1, vector<pt>(2));
	forn(i, n - 1) forn(j, 2){
		scanf("%d%d", &d[i][j].x, &d[i][j].y);
		--d[i][j].x, --d[i][j].y;
	}
	int lg = 1;
	while ((1 << lg) < n - 1) ++lg;
	vector<vector<vector<vector<long long>>>> dp(n - 2, vector<vector<vector<long long>>>(lg, vector<vector<long long>>(2, vector<long long>(2, INF64))));
	forn(i, n - 2) forn(k, 2){
		dp[i][0][0][k] = abs(d[i][0].x + 1 - d[i + 1][k].x) + abs(d[i][0].y - d[i + 1][k].y) + 1;
		dp[i][0][1][k] = abs(d[i][1].x - d[i + 1][k].x) + abs(d[i][1].y + 1 - d[i + 1][k].y) + 1;
	}
	for (int l = 1; l < lg; ++l) forn(i, n - 2) forn(j, 2) forn(k, 2) forn(t, 2) if (i + (1 << (l - 1)) < n - 2){
		dp[i][l][j][k] = min(dp[i][l][j][k], dp[i][l - 1][j][t] + dp[i + (1 << (l - 1))][l - 1][t][k]);
	}
	int m;
	scanf("%d", &m);
	forn(_, m){
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		--x1, --y1, --x2, --y2;
		int l1 = max(x1, y1), l2 = max(x2, y2);
		if (l1 > l2){
			swap(l1, l2);
			swap(x1, x2);
			swap(y1, y2);
		}
		if (l1 == l2){
			printf("%d\n", abs(x1 - x2) + abs(y1 - y2));
			continue;
		}
		vector<long long> ndp(2);
		ndp[0] = abs(x1 - d[l1][0].x) + abs(y1 - d[l1][0].y);
		ndp[1] = abs(x1 - d[l1][1].x) + abs(y1 - d[l1][1].y);
		for (int i = lg - 1; i >= 0; --i) if (l1 + (1 << i) < l2){
			vector<long long> tmp(2, INF64);
			forn(j, 2) forn(k, 2)
				tmp[k] = min(tmp[k], ndp[j] + dp[l1][i][j][k]);
			ndp = tmp;
			l1 += (1 << i);
		}
		long long ans = INF64;
		ans = min(ans, ndp[0] + abs(d[l1][0].x + 1 - x2) + abs(d[l1][0].y - y2) + 1);
		ans = min(ans, ndp[1] + abs(d[l1][1].x - x2) + abs(d[l1][1].y + 1 - y2) + 1);
		printf("%lld\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct edge{
	int u, w;
};

int n;
vector<vector<edge>> g;
vector<vector<int>> ng;
vector<int> tin, tout, siz, ord;
int T;

vector<int> pw;

void init(int v, int p = -1){
	tin[v] = T++;
	ord.push_back(v);
	siz[v] = 1;
	for (const auto &it : g[v]){
		int u = it.u, w = it.w;
		if (u == p) continue;
		pw[u] = w;
		init(u, v);
		siz[v] += siz[u];
	}
	tout[v] = T;
}

int isp(int v, int u){
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

vector<int> nsiz;
vector<vector<int>> dp;

long long dfs(int v, int x){
	long long res = 0;
	for (int u : ng[v])
		res += dfs(u, x);
	dp[v][0] = siz[v];
	dp[v][1] = 0;
	for (int u : ng[v]) dp[v][0] -= siz[u];
	for (int u : ng[v]){
		if (pw[u] == x){
			res += dp[u][0] * 1ll * dp[v][0];
			dp[v][1] += dp[u][0];
		}
		else{
			res += dp[u][0] * 1ll * dp[v][1];
			res += dp[u][1] * 1ll * dp[v][0];
			dp[v][0] += dp[u][0];
			dp[v][1] += dp[u][1];
		}
	}
	return res;
}

int main() {
	scanf("%d", &n);
	
	g.resize(n);
	forn(i, n - 1){
		int v, u, w;
		scanf("%d%d%d", &v, &u, &w);
		--v, --u, --w;
		g[v].push_back({u, w});
		g[u].push_back({v, w});
	}
	
	T = 0;
	tin.resize(n);
	tout.resize(n);
	siz.resize(n);
	pw.resize(n, -1);
	init(0);
	
	vector<vector<int>> sv(n, vector<int>(1, 0));
	for (int v : ord) for (auto it : g[v])
		sv[it.w].push_back(v);
	
	ng.resize(n);
	nsiz.resize(n);
	dp.resize(n, vector<int>(2));
	long long ans = 0;
	forn(i, n) if (!sv[i].empty()){
		sv[i].resize(unique(sv[i].begin(), sv[i].end()) - sv[i].begin());
		vector<int> st;
		for (int v : sv[i]){
			while (!st.empty() && !isp(st.back(), v))
				st.pop_back();
			if (!st.empty())
				ng[st.back()].push_back(v);
			st.push_back(v);
		}
		ans += dfs(0, i);
		
		for (int v : sv[i]) ng[v].clear();
	}
	
	printf("%lld\n", ans);
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct edge{
	int v, u, w;
};

vector<vector<edge>> t;

void add(int v, int l, int r, int L, int R, const edge &e){
	if (L >= R)
		return;
	if (l == L && r == R){
		t[v].push_back(e);
		return;
	}
	int m = (l + r) / 2;
	add(v * 2, l, m, L, min(m, R), e);
	add(v * 2 + 1, m, r, max(m, L), R, e);
}

vector<int> rk, p;
vector<int*> where;
vector<int> val;

int getp(int a){
	return a == p[a] ? a : getp(p[a]);
}

void unite(int a, int b){
	a = getp(a), b = getp(b);
	if (a == b) return;
	if (rk[a] < rk[b]) swap(a, b);
	where.push_back(&rk[a]);
	val.push_back(rk[a]);
	rk[a] += rk[b];
	where.push_back(&p[b]);
	val.push_back(p[b]);
	p[b] = a;
}

void rollback(){
	*where.back() = val.back();
	where.pop_back();
	val.pop_back();
}

long long trav(int v, int l, int r){
	int sv = where.size();
	for (auto it : t[v]) if (it.w == 0)
		unite(it.v, it.u);
	long long res = 0;
	if (l == r - 1){
		for (auto it : t[v]) if (it.w == 1)
			res += rk[getp(it.v)] * 1ll * rk[getp(it.u)];
	}
	else{
		int m = (l + r) / 2;
		res += trav(v * 2, l, m);
		res += trav(v * 2 + 1, m, r);
	}
	while (int(where.size()) > sv) rollback();
	return res;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<edge> e(n - 1);
	forn(i, n - 1){
		scanf("%d%d%d", &e[i].v, &e[i].u, &e[i].w);
		--e[i].v, --e[i].u, --e[i].w;
	}
	sort(e.begin(), e.end(), [](const edge &a, const edge &b){
		return a.w < b.w;
	});
	t.resize(4 * n);
	forn(i, n - 1){
		int pos = lower_bound(e.begin(), e.end(), e[i], [](const edge &a, const edge &b){
			return a.w < b.w;
		}) - e.begin();
		add(1, 0, n, 0, pos, {e[i].v, e[i].u, 0});
		add(1, 0, n, pos, pos + 1, {e[i].v, e[i].u, 1});
		add(1, 0, n, pos + 1, n, {e[i].v, e[i].u, 0});
	}
	rk.resize(n, 1);
	p.resize(n);
	iota(p.begin(), p.end(), 0);
	printf("%lld\n", trav(1, 0, n));
	return 0;
}

t = int(input())
for i in range(t):
    l1, r1, l2, r2 = map(int, input().split())
    if max(l1, l2) <= min(r1, r2):
        print(max(l1, l2))
    else:
        print(l1 + l2)

t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    s = []
    for j in range(n):
        s.append(input())
    minx = 10 ** 9
    miny = 10 ** 9
    for x in range(n):
        for y in range(m):
            if s[x][y] == 'R':
                minx = min(minx, x)
                miny = min(miny, y)
    print('YES' if s[minx][miny] == 'R' else 'NO')

def can(pos, m):
    k = len(pos) 
    x = k - m
    for i in range(m + 1):
        l = pos[i]
        r = pos[i + x - 1]
        if r - l + 1 - x <= m:
            return True
    return False    

t = int(input())
for i in range(t):
    s = input()
    pos = []
    n = len(s)
    for i in range(n):
        if s[i] == '1':
            pos.append(i)
    lf = 0
    rg = len(pos)
    while rg - lf > 1:
        mid = (lf + rg) // 2
        if can(pos, mid):
            rg = mid
        else:
            lf = mid
    if len(pos) == 0 or pos[-1] - pos[0] == len(pos) - 1:
        print(0)
    else:
        print(rg)

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &it : a) {
        cin >> it;
    }
    
    long long ans = 0;
    for (int it = 0; it < n; ++it) {
        vector<int> cnt(n);
        for (int i = n - 1; i >= 0; --i) {
            cnt[i] = (a[i] == 0);
            if (i + 1 < n) {
                cnt[i] += cnt[i + 1];
            }
        }
        vector<long long> b = a;
        long long s = accumulate(b.begin(), b.end(), 0ll);
        bool ok = true;
        for (int i = 0; i < n; ++i) {
            if (b[i] == 0) {
                long long x = (i + 1 < n ? cnt[i + 1] : 0);
                b[i] = min(k, x * k - s);
                if (b[i] < -k) {
                    ok = false;
                }
                s += b[i];
            }
        }
        if (ok) {
            long long pos = 0, mn = 0, mx = 0;
            for (int i = 0; i < n; ++i) {
                pos += b[i];
                mn = min(mn, pos);
                mx = max(mx, pos);
            }
            if (pos == 0) {
                ans = max(ans, mx - mn + 1);
            }
        }
        rotate(a.begin(), a.begin() + 1, a.end());
    }
    
    if (ans == 0) {
        ans = -1;
    }
    
    cout << ans << endl;
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        string s[2];
        cin >> n >> s[0] >> s[1];
        
        for (int it = 0; it < 2; ++it) {
            while (s[0].back() == '.' && s[1].back() == '.') {
                s[0].pop_back();
                s[1].pop_back();
            }
            reverse(s[0].begin(), s[0].end());
            reverse(s[1].begin(), s[1].end());
        }
        n = s[0].size();
        
        vector<vector<int>> cost(n, vector<int>(2));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 2; ++j) {
                cost[i][j] = (s[j][i] == '*');
            }
        }
        
        vector<vector<int>> dp(n, vector<int>(2, INF));
        dp[0][0] = cost[0][1];
        dp[0][1] = cost[0][0];
        for (int i = 0; i + 1 < n; ++i) {
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + 1 + cost[i + 1][1]);
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + 2);
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1 + cost[i + 1][0]);
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 2);
        }
        
        cout << min(dp[n - 1][0], dp[n - 1][1]) << endl;
    }
        
    return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

vector<vector<int>> g, h;
vector<int> tin, tout, clr;
vector<vector<int>> sum(2);
int T;

int flip;
int cnt;

bool isp(int v, int u){
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}

void init(int v){
    tin[v] = T++;
    for (int u : g[v]){
        if (clr[u] == -1){
            clr[u] = clr[v] ^ 1;
            h[v].push_back(u);
            init(u);
        }
        else if (tin[u] < tin[v]){
            int dif = clr[v] ^ clr[u];
            if (!dif){
                flip = clr[v] ^ 1;
                ++cnt;
            }
            --sum[dif][u];
            ++sum[dif][v]; 
        }
    }
    tout[v] = T;
}

int sv;

void dfs(int v){
    for (int u : h[v]){
        dfs(u);
        if (sum[0][u] == cnt && sum[1][u] == 1){
            sv = u;
            flip = clr[v] ^ 1;
        }
        forn(i, 2) sum[i][v] += sum[i][u];
    }
}

int main() {
    cin.tie(0);
    iostream::sync_with_stdio(false);
    int t;
    cin >> t;
    forn(_, t){
        int n, m;
        cin >> n >> m;
        g.assign(n, vector<int>());
        h.assign(n, vector<int>());
        forn(i, m){
            int v, u;
            cin >> v >> u;
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        tin.resize(n);
        tout.resize(n);
        forn(i, 2) sum[i].assign(n, 0);
        clr.assign(n, -1);
        cnt = 0;
        T = 0;
        clr[0] = 0;
        init(0);
        if (cnt <= 1){
            cout << "YES\n";
            forn(v, n) cout << (clr[v] ^ flip);
            cout << "\n";
            continue;
        }
        sv = -1;
        dfs(0);
        if (sv == -1){
            cout << "NO\n";
        }
        else{
            cout << "YES\n";
            forn(v, n) cout << (clr[v] ^ isp(sv, v) ^ flip);
            cout << "\n";
        }
    }
    return 0;
}

t = int(input())
for i in range(t):
    s = input()
    ans = True
    n = len(s)
    for j in range(n):
        if (j == 0 or s[j] != s[j - 1]) and (j == n - 1 or s[j] != s[j + 1]):
            ans = False
    print('YES' if ans else 'NO')

for i in range(int(input())):
    n = int(input())
    x = list(map(int, input().split()))
    print('YES' if x[-1] - x[0] - n + 1 <= 2 else 'NO')

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, x) = readLine()!!.split(' ').map { it.toInt() }
        val a = readLine()!!.split(' ').map { it.toInt() }.sorted()

        var sum = a.sumOf { it.toLong() }
        var prevDay = -1L
        var ans = 0L
        for (i in n - 1 downTo 0) {
            val curDay = if (x - sum >= 0) (x - sum) / (i + 1) else -1
            ans += (i + 1) * (curDay - prevDay)
            prevDay = curDay
            sum -= a[i]
        }
        println(ans)
    }
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;


int main() {
    int t;
    scanf("%d", &t);
    forn(_, t){
        int n, x;
        scanf("%d%d", &n, &x);
        vector<int> a(n);
        forn(i, n) scanf("%d", &a[i]);
        long long ans = 1e18;
        long long cur = 0;
        forn(i, n - 1){
            cur += abs(a[i] - a[i + 1]);
        }
        forn(_, 2){
            long long mn = abs(a[0] - 1);
            ans = min(ans, cur + abs(a[0] - x) + (x - 1));
            forn(i, n - 1){
                ans = min(ans, cur + mn - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - x));
                ans = min(ans, cur - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - 1) + (x - 1));
                mn = min(mn, 0ll - abs(a[i] - a[i + 1]) + abs(a[i] - 1) + abs(a[i + 1] - 1));
            }
            ans = min(ans, cur + mn + abs(a.back() - x));
            reverse(a.begin(), a.end());
        }
        printf("%lld\n", ans);
    }
    return 0;
}

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

mt19937 rnd(42);

const int MOD = 998244353;
const int K = 3;

int add(int x, int y, int mod = MOD)
{
    x += y;
    while(x >= mod) x -= mod;
    while(x < 0) x += mod;
    return x;
}   

int sub(int x, int y, int mod = MOD)
{
    return add(x, -y, mod);
}   

int mul(int x, int y, int mod = MOD)
{
    return (x * 1ll * y) % mod;
}

int binpow(int x, int y, int mod = MOD)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x, mod);
        y /= 2;
        x = mul(x, x, mod);
    }   
    return z;
}

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

int get_base()
{
    int x = rnd() % 10000 + 4444;
    while(!prime(x)) x++;
    return x;
}   

int get_modulo()
{
    int x = rnd() % int(1e9) + int(1e8);
    while(!prime(x)) x++;
    return x;
}   

typedef array<int, K> hs;

hs base, modulo;

void generate_hs()
{
    for(int i = 0; i < K; i++)
    {
        base[i] = get_base();
        modulo[i] = get_modulo();
    }
}   

hs operator+(const hs& a, const hs& b)
{
    hs c;
    for(int i = 0; i < K; i++)
    {
        c[i] = add(a[i], b[i], modulo[i]);    
    }
    return c;
}

hs operator-(const hs& a, const hs& b)
{
    hs c;
    for(int i = 0; i < K; i++)
    {
        c[i] = sub(a[i], b[i], modulo[i]);    
    }
    return c;
}

hs operator*(const hs& a, const hs& b)
{
    hs c;
    for(int i = 0; i < K; i++)
    {
        c[i] = mul(a[i], b[i], modulo[i]);    
    }
    return c;
}

hs operator^(const hs& a, const hs& b)
{
    hs c; 
    for(int i = 0; i < K; i++)
    {
        c[i] = binpow(a[i], b[i], modulo[i]);    
    }
    return c;
}

hs char_hash(char c)
{
    hs res;
    for(int i = 0; i < K; i++)
        res[i] = c - 'A' + 1;
    return res;
}

const int N = 18;
const int V = 1 << N;
string s;
char buf[V + 43];
int n;
int ans[V + 43];
hs vertex_hash[V + 43];

bool is_leaf(int x)
{
    return (x * 2 + 1) >= ((1 << n) - 1);
}

void rec(int x)
{
    vertex_hash[x] = char_hash(s[x]);
    ans[x] = 1;
    if(is_leaf(x)) 
    {
        return;
    }
    rec(x * 2 + 1);
    rec(x * 2 + 2);
    vertex_hash[x] = vertex_hash[x] + (base ^ vertex_hash[2 * x + 1]) + (base ^ vertex_hash[2 * x + 2]);
    ans[x] = mul(ans[2 * x + 1], ans[2 * x + 2]);
    if(vertex_hash[2 * x + 1] != vertex_hash[2 * x + 2])
        ans[x] = mul(ans[x], 2);
}
 
int main() 
{
    generate_hs();
    scanf("%d", &n);
    scanf("%s", buf);
    s = buf;
    rec(0);
    cout << ans[0] << endl;
}

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

const int K = 13;
const int MOD = 998244353;

int n, k, x;

int cnt[K][K][K];
int dp[K][2 * K][K][K];

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}   

int sub(int x, int y)
{
    return add(x, -y);
}   

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        y /= 2;
        x = mul(x, x);
    }   
    return z;
}

void precalc()
{
    cnt[2][1][1] = 1;
    cnt[3][1][2] = 2;
    cnt[3][2][3] = 1;
    cnt[4][1][3] = 3;
    cnt[4][1][4] = 1;
    cnt[4][2][3] = 1;
    cnt[4][2][4] = 4;
    cnt[4][2][5] = 3;
    cnt[4][3][6] = 1;
    cnt[5][1][4] = 4;
    cnt[5][1][5] = 2;
    cnt[5][1][6] = 2;
    cnt[5][2][4] = 4;
    cnt[5][2][5] = 12;
    cnt[5][2][6] = 12;
    cnt[5][2][7] = 9;
    cnt[5][2][8] = 3;
    cnt[5][3][5] = 2;
    cnt[5][3][6] = 4;
    cnt[5][3][7] = 6;
    cnt[5][3][8] = 6;
    cnt[5][3][9] = 4;
    cnt[5][4][10] = 1;
    cnt[6][1][5] = 5;
    cnt[6][1][6] = 3;
    cnt[6][1][7] = 4;
    cnt[6][1][8] = 3;
    cnt[6][1][9] = 1;
    cnt[6][2][5] = 10;
    cnt[6][2][6] = 28;
    cnt[6][2][7] = 35;
    cnt[6][2][8] = 35;
    cnt[6][2][9] = 30;
    cnt[6][2][10] = 17;
    cnt[6][2][11] = 8;
    cnt[6][3][5] = 1;
    cnt[6][3][6] = 13;
    cnt[6][3][7] = 29;
    cnt[6][3][8] = 41;
    cnt[6][3][9] = 44;
    cnt[6][3][10] = 45;
    cnt[6][3][11] = 30;
    cnt[6][4][7] = 1;
    cnt[6][4][8] = 4;
    cnt[6][4][9] = 7;
    cnt[6][4][10] = 7;
    cnt[6][4][11] = 11;
    cnt[7][1][6] = 6;
    cnt[7][1][7] = 4;
    cnt[7][1][8] = 6;
    cnt[7][1][9] = 6;
    cnt[7][1][10] = 6;
    cnt[7][1][11] = 2;
    cnt[7][2][6] = 20;
    cnt[7][2][7] = 55;
    cnt[7][2][8] = 80;
    cnt[7][2][9] = 95;
    cnt[7][2][10] = 101;
    cnt[7][2][11] = 94;
    cnt[7][3][6] = 6;
    cnt[7][3][7] = 50;
    cnt[7][3][8] = 118;
    cnt[7][3][9] = 186;
    cnt[7][3][10] = 230;
    cnt[7][3][11] = 260;
    cnt[7][4][7] = 3;
    cnt[7][4][8] = 18;
    cnt[7][4][9] = 48;
    cnt[7][4][10] = 85;
    cnt[7][4][11] = 113;
    cnt[7][5][10] = 2;
    cnt[7][5][11] = 4;
    cnt[8][1][7] = 7;
    cnt[8][1][8] = 5;
    cnt[8][1][9] = 8;
    cnt[8][1][10] = 9;
    cnt[8][1][11] = 11;
    cnt[8][2][7] = 35;
    cnt[8][2][8] = 96;
    cnt[8][2][9] = 155;
    cnt[8][2][10] = 207;
    cnt[8][2][11] = 250;
    cnt[8][3][7] = 21;
    cnt[8][3][8] = 145;
    cnt[8][3][9] = 358;
    cnt[8][3][10] = 616;
    cnt[8][3][11] = 859;
    cnt[8][4][7] = 1;
    cnt[8][4][8] = 26;
    cnt[8][4][9] = 124;
    cnt[8][4][10] = 313;
    cnt[8][4][11] = 567;
    cnt[8][5][9] = 3;
    cnt[8][5][10] = 16;
    cnt[8][5][11] = 53;
    cnt[9][1][8] = 8;
    cnt[9][1][9] = 6;
    cnt[9][1][10] = 10;
    cnt[9][1][11] = 12;
    cnt[9][2][8] = 56;
    cnt[9][2][9] = 154;
    cnt[9][2][10] = 268;
    cnt[9][2][11] = 389;
    cnt[9][3][8] = 56;
    cnt[9][3][9] = 350;
    cnt[9][3][10] = 898;
    cnt[9][3][11] = 1654;
    cnt[9][4][8] = 8;
    cnt[9][4][9] = 126;
    cnt[9][4][10] = 552;
    cnt[9][4][11] = 1404;
    cnt[9][5][9] = 4;
    cnt[9][5][10] = 48;
    cnt[9][5][11] = 204;
    cnt[9][6][11] = 1;
    cnt[10][1][9] = 9;
    cnt[10][1][10] = 7;
    cnt[10][1][11] = 12;
    cnt[10][2][9] = 84;
    cnt[10][2][10] = 232;
    cnt[10][2][11] = 427;
    cnt[10][3][9] = 126;
    cnt[10][3][10] = 742;
    cnt[10][3][11] = 1967;
    cnt[10][4][9] = 36;
    cnt[10][4][10] = 448;
    cnt[10][4][11] = 1887;
    cnt[10][5][9] = 1;
    cnt[10][5][10] = 43;
    cnt[10][5][11] = 357;
    cnt[10][6][11] = 6;
    cnt[11][1][10] = 10;
    cnt[11][1][11] = 8;
    cnt[11][2][10] = 120;
    cnt[11][2][11] = 333;
    cnt[11][3][10] = 252;
    cnt[11][3][11] = 1428;
    cnt[11][4][10] = 120;
    cnt[11][4][11] = 1302;
    cnt[11][5][10] = 10;
    cnt[11][5][11] = 252;
    cnt[11][6][11] = 5;
    cnt[12][1][11] = 11;
    cnt[12][2][11] = 165;
    cnt[12][3][11] = 462;
    cnt[12][4][11] = 330;
    cnt[12][5][11] = 55;
    cnt[12][6][11] = 1;    
}

int inv[K];

int C(int n, int k)
{
    if(n < 0 || n < k || k < 0) return 0;
    int res = 1;
    for(int i = n; i > n - k; i--)
        res = mul(res, i);
    for(int i = 1; i <= k; i++)
        res = mul(res, inv[i]);
    return res;
}

void prepare()
{
    for(int i = 1; i < K; i++)
        inv[i] = binpow(i, MOD - 2);
    precalc();
    dp[0][0][0][0] = 1;
    for(int i = 0; i < K; i++)
        for(int j = 0; j < 2 * K; j++)
            for(int a = 0; a < K - 2; a++)
                for(int b = 0; b < K - 2; b++)
                {
                    if(dp[i][j][a][b] == 0) continue;
                    for(int add_cnt = 2; add_cnt < K; add_cnt++)
                        for(int add_desc = 1; add_desc <= K - 2; add_desc++)
                            for(int add_inv = 1; add_inv <= K - 2; add_inv++)
                            {
                                if(j + add_cnt >= 2 * K || a + add_desc > K - 2 || b + add_inv > K - 2) continue;
                                int& nw = dp[i + 1][j + add_cnt][a + add_desc][b + add_inv];
                                nw = add(nw, mul(dp[i][j][a][b], cnt[add_cnt][add_desc][add_inv]));    
                            }
                }       
}

void solve() 
{
    scanf("%d %d %d", &n, &k, &x);
    if(k == 0 && x == 0)
    {
        puts("1");
        return;
    }
    int ans = 0;
    for(int i = 1; i < K; i++)
        for(int j = 1; j < 2 * K; j++)
            if(dp[i][j][x][k] != 0)
            {
                ans = add(ans, mul(dp[i][j][x][k], C(n - j + i, i)));        
            }
    printf("%d\n", ans);
}

int main()
{
    prepare();
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++)
        solve();
}