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();
}

import kotlin.math.abs

fun sum(a1: Int, a2: Int, b1: Int, b2: Int) = abs(a1 - a2) + abs(b1 - b2)

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

        var sum = 0L
        for (i in 1 until n) {
            if (sum(a[i - 1], a[i], b[i - 1], b[i]) > sum(a[i - 1], b[i], b[i - 1], a[i]))
                a[i] = b[i].also { b[i] = a[i] }
            sum += sum(a[i - 1], a[i], b[i - 1], b[i])
        }
        println(sum)
    }
}

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

    for (v in a) {
        var ans = 20
        for (cntAdd in 0..15) {
            for (cntMul in 0..15) {
                if (((v + cntAdd) shl cntMul) % 32768 == 0)
                    ans = minOf(ans, cntAdd + cntMul)
            }
        }
        print("$ans ")
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int tc;
    scanf("%d", &tc);
    while (tc--) {
        int n;
        scanf("%d", &n);
        vector<int> h(n);
        for (auto &it : h) {
            scanf("%d", &it);
        }
        
        int mx = *max_element(h.begin(), h.end());
        long long ans = 1e18;
        for (auto need : {mx, mx + 1}) {
            long long l = 0, r = 1e18;
            long long res = -1;
            while (l <= r) {
                long long mid = (l + r) >> 1;
                long long cnt1 = (mid + 1) / 2, cnt2 = mid - cnt1;
                long long need1 = 0;
                for (auto ch : h) {
                    long long cur = (need - ch) / 2;
                    if ((need - ch) % 2 == 1) {
                        ++need1;
                    }
                    if (cnt2 >= cur) {
                        cnt2 -= cur;
                    } else {
                        cur -= cnt2;
                        cnt2 = 0;
                        need1 += cur * 2;
                    }
                }
                if (need1 <= cnt1) {
                    res = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            ans = min(ans, res);
        }
        
        printf("%lld\n", ans);
    }
        
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main(){
    int tc;
    scanf("%d", &tc);
    while (tc--) {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        forn(i, n) scanf("%d", &a[i]);
        long long ans = 1e18;
        int mx = *max_element(a.begin(), a.end());
        for (int x : {mx, mx + 1}){
            long long cnt1 = 0, cnt2 = 0;
            forn(i, n){
                cnt2 += (x - a[i]) / 2;
                cnt1 += (x - a[i]) % 2;
            }
            long long dif = max(0ll, cnt2 - cnt1 - 1) / 3;
            cnt1 += dif * 2;
            cnt2 -= dif;
            ans = min(ans, max(cnt1 * 2 - 1, cnt2 * 2));
            if (cnt2 > 0){
                cnt1 += 2;
                --cnt2;
                ans = min(ans, max(cnt1 * 2 - 1, cnt2 * 2));
            }
        }
        printf("%lld\n", ans);
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif

    int n, k;
    scanf("%d %d", &n, &k);
    vector<long long> b(n);
    for (auto &it : b) {
        scanf("%lld", &it);
    }
    
    vector<long long> closed(n);
    long long sum = 0, cnt = 0, ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        sum -= cnt;
        cnt -= closed[i];
        b[i] -= sum;
        if (b[i] <= 0) {
            continue;
        }
        int el = min(i + 1, k);
        long long need = (b[i] + el - 1) / el;
        sum += need * el;
        cnt += need;
        ans += need;
        if (i - el >= 0) {
            closed[i - el] += need;
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main(){
    cin.tie(0);
	iostream::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<string> s(3);
	forn(i, 3) cin >> s[i];
	vector<int> pr(n + 1);
	forn(i, n){
		pr[i + 1] += pr[i];
		forn(j, 3) pr[i + 1] += (s[j][i] == '1');
	}
	
	vector<int> p(3 * n), rk(3 * n, 1);
	iota(p.begin(), p.end(), 0);
	function<int(int)> getp;
	getp = [&](int a) -> int {
		return a == p[a] ? a : p[a] = getp(p[a]);
	};
	auto unite = [&](int a, int b) -> bool {
		a = getp(a), b = getp(b);
		if (a == b) return false;
		if (rk[a] < rk[b]) swap(a, b);
		p[b] = a;
		rk[a] += rk[b];
		return true;
	};
	
	vector<int> prhe(n + 1), prve(n + 1);
	
	forn(j, n){
		forn(i, 2) if (s[i][j] == '1' && s[i + 1][j] == '1' && unite(i * n + j, (i + 1) * n + j))
			++prve[j + 1];
		forn(i, 3) if (j > 0 && s[i][j] == '1' && s[i][j - 1] == '1' && unite(i * n + j, i * n + (j - 1)))
			++prhe[j];
	}
	forn(i, n) prve[i + 1] += prve[i];
	forn(i, n) prhe[i + 1] += prhe[i];
	
	vector<int> nxt(n + 1, 0);
	for (int i = n - 1; i >= 0; --i)
		nxt[i] = (s[0][i] == '1' && s[1][i] == '0' && s[2][i] == '1' ? (nxt[i + 1] + 1) : 0);
	
	int m;
	cin >> m;
	forn(_, m){
		int l, r;
		cin >> l >> r;
		--l, --r;
		int non101 = l + nxt[l];
		if (non101 > r){
		    cout << "2\n";
		    continue;
		}
		int tot = pr[r + 1] - pr[non101];
		int in = (prve[r + 1] - prve[non101]) + (prhe[r] - prhe[non101]);
		int res = tot - in;
		if (non101 != l){
			if (s[0][non101] == '1' && s[1][non101] == '1' && s[2][non101] == '1');
			else if (s[0][non101] == '0' && s[2][non101] == '0') res += 2;
			else ++res;
		}
		cout << res << "\n";
	}
	
	return 0;
}

#include <bits/stdc++.h>     

using namespace std;

int n;
vector<int> lens;

long long sqr(int x)
{
    return x * 1ll * x;
}

long long eval_split(int len, int k)
{
    return sqr(len / k) * (k - len % k) + sqr(len / k + 1) * (len % k);
}

pair<int, long long> eval_segment(int len, long long bound)
{
    // only take options with value >= bound
    if(bound <= 2 || len == 1)
        return make_pair(len - 1, len);
    int lf = 0;
    int rg = len - 1;
    while(rg - lf > 1)
    {
        int mid = (lf + rg) / 2;
        if(eval_split(len, mid) - eval_split(len, mid + 1) >= bound)
            lf = mid;
        else
            rg = mid;    
    }
    return make_pair(lf, eval_split(len, lf + 1));
}

pair<int, long long> eval_full(long long bound)
{
    pair<int, long long> ans;
    for(auto x : lens)
    {
        pair<int, long long> cur = eval_segment(x, bound);
        ans.first += cur.first;
        ans.second += cur.second;
    }
    return ans;
}

int main()
{
    scanf("%d", &n);
    int pr = 0;
    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        lens.push_back(x - pr);
        pr = x;
    }
    long long w;
    scanf("%lld", &w);
    long long lf = 0ll;
    long long rg = (long long)(1e18) + 43;
    if(eval_full(rg).second <= w)
    {
        cout << 0 << endl;
        return 0;
    }
    while(rg - lf > 1)
    {
        long long mid = (lf + rg) / 2;
        pair<int, long long> res = eval_full(mid);
        if(res.second <= w)
            lf = mid;
        else
            rg = mid;
    }   
    pair<int, long long> resL = eval_full(lf);
    pair<int, long long> resR = eval_full(rg);
    assert(resL.second <= w && resR.second > w);
    long long change = (resR.second - resL.second) / (resR.first - resL.first);
    cout << resL.first + (w - resL.second) / change << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int x, y;
    cin >> x >> y;
    int d = x * x + y * y;
    int r = 0;
    while (r * r < d) ++r;
    int ans = 2;
    if (r * r == d) ans = 1;
    if (x == 0 && y == 0) ans = 0; 
    cout << ans << '\n';
  }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, B, x, y) = readLine()!!.split(' ').map { it.toInt() }
        var cur = 0L
        var ans = 0L
        for (i in 1..n) {
            cur += if (cur + x <= B) x else -y
            ans += cur
        }
        println(ans)
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        int l = 0;
        int cnt = 0;
        while (l + 1 < n) {
            if (s[l] == '(' || (s[l] == ')' && s[l + 1] == ')')) {
                l += 2;
            } else {
                int r = l + 1;
                while (r < n && s[r] != ')') {
                    ++r;
                }
                if (r == n) {
                    break;
                }
                l = r + 1;
            }
            ++cnt;
        }
        cout << cnt << ' ' << n - l << '\n';
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main(){
	int n, C;
	scanf("%d%d", &n, &C);
	vector<long long> bst(C + 1);
	forn(i, n){
		int c, d, h;
		scanf("%d%d%d", &c, &d, &h);
		bst[c] = max(bst[c], d * 1ll * h);
	}
	for (int c = 1; c <= C; ++c) for (int xc = c; xc <= C; xc += c)
		bst[xc] = max(bst[xc], bst[c] * (xc / c));
	forn(c, C)
		bst[c + 1] = max(bst[c + 1], bst[c]);
	int m;
	scanf("%d", &m);
	forn(j, m){
		int D;
		long long H;
		scanf("%d%lld", &D, &H);
		int mn = upper_bound(bst.begin(), bst.end(), D * H) - bst.begin();
		if (mn > C) mn = -1;
		printf("%d ", mn);
	}
	puts("");
}

#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 998244353;

int add(int a, int b){
	a += b;
	if (a >= MOD)
		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 n, k;
	scanf("%d%d", &n, &k);
	--n;
	vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
	vector<vector<int>> C(n + 1);
	forn(i, n + 1){
		C[i].resize(i + 1);
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; ++j)
			C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
	}
	dp[0][0] = 1;
	forn(i, k) forn(t, n + 1) {
		int pw = binpow(k - i, t * (t - 1) / 2);
		int step = binpow(k - i, t);
		forn(j, n - t + 1){
			dp[i + 1][j + t] = add(dp[i + 1][j + t], mul(dp[i][j], mul(C[n - j][t], pw)));
			pw = mul(pw, step);
		}
	}
	printf("%d\n", dp[k][n]);
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
 
vector<vector<int>> t;
vector<int> p, h;
 
void init(int v){
	for (int u : t[v]) if (u != p[v]){
		p[u] = v;
		h[u] = h[v] + 1;
		init(u);
	}
}
 
vector<int> get_path(int v, int u){
	vector<int> l, r;
	while (v != u){
		if (h[v] > h[u]){
			l.push_back(v);
			v = p[v];
		}
		else{
			r.push_back(u);
			u = p[u];
		}
	}
	l.push_back(v);
	while (!r.empty()){
		l.push_back(r.back());
		r.pop_back();
	}
	return l;
}
 
vector<vector<int>> g, tg;
 
void add_edge(int v, bool vx, int u, bool vy){
	// (val[v] == vx) -> (val[u] == vy)
	g[v * 2 + vx].push_back(u * 2 + vy);
	tg[u * 2 + vy].push_back(v * 2 + vx);
	g[u * 2 + !vy].push_back(v * 2 + !vx);
	tg[v * 2 + !vx].push_back(u * 2 + !vy);
}
 
vector<int> ord;
vector<char> used;
 
void ts(int v){
	used[v] = true;
	for (int u : g[v]) if (!used[u])
		ts(u);
	ord.push_back(v);
}
 
vector<int> clr;
int k;
 
void dfs(int v){
	clr[v] = k;
	for (int u : tg[v]) if (clr[u] == -1)
		dfs(u);
}
 
int main(){
	cin.tie(0);
	iostream::sync_with_stdio(false);
	
	int n, m;
	cin >> n >> m;
	t.resize(n);
	p.resize(n);
	h.resize(n);
	p[0] = -1;
	forn(i, n - 1){
		int v, u;
		cin >> v >> u;
		--v, --u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	init(0);
	
	vector<vector<int>> paths(m);
	vector<string> s(m);
	
	vector<pair<char, char>> opts(n, make_pair(-1, -1));
	forn(i, m){
		int v, u;
		cin >> v >> u >> s[i];
		--v, --u;
		paths[i] = get_path(v, u);
		int k = s[i].size();
		assert(int(paths[i].size()) == k);
		forn(j, k) opts[paths[i][j]] = {s[i][j], s[i][k - j - 1]};
	}
	
	int nm = (n + m) * 2;
	g.resize(nm);
	tg.resize(nm);
	forn(i, m){
		int k = s[i].size();
		forn(j, k){
			int v = paths[i][j];
			char c = s[i][j], rc = s[i][k - j - 1];
			char d = opts[v].first, rd = opts[v].second;
			if (d != c) add_edge(v, false, n + i, true);
			if (d != rc) add_edge(v, false, n + i, false);
			if (rd != c) add_edge(v, true, n + i, true);
			if (rd != rc) add_edge(v, true, n + i, false);
		}
	}
	
	used.resize(nm);
	forn(i, nm) if (!used[i]) ts(i);
	clr.resize(nm, -1);
	reverse(ord.begin(), ord.end());
	for (int v : ord) if (clr[v] == -1){
		dfs(v);
		++k;
	}
	forn(i, nm) if (clr[i] == clr[i ^ 1]){
		cout << "NO\n";
		return 0;
	}
	
	cout << "YES\n";
	for (int i = 0; i < 2 * n; i += 2){
		if (opts[i / 2].first == -1)
			cout << 'a';
		else if (clr[i] > clr[i ^ 1])
			cout << opts[i / 2].first;
		else
			cout << opts[i / 2].second;
	}
	cout << "\n";
}

t = int(input())
for i in range(t):
    n = int(input())
    print(2 ** n - 1)

for _ in range(int(input())):
	n = int(input())
	if 3**(n-1) > 10**9:
		print("NO")
	else:
		print("YES")
		print(*[3**x for x in range(n)])

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

typedef long long li;

const int INF = int(1e9);

int n;
vector<int> a, b;

inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	b.resize(n);
	fore (i, 0, n)
		cin >> b[i];
	return true;
}

int bestCandidate(const vector<int> &vals, int cur) {
	int bst = INF + 10, pos = -1;
	fore (i, 0, n) {
		if (bst > abs(cur - vals[i])) {
			bst = abs(cur - vals[i]);
			pos = i;
		}
	}
	return pos;
}

inline void solve() {
	li bst = 10ll * INF;
	
	vector<int> cds1 = {0, bestCandidate(b, a[0]), n - 1};
	vector<int> cds2 = {0, bestCandidate(b, a[n - 1]), n - 1};
	
	for (int var1 : cds1) {
		for (int var2 : cds2) {
			li ans = (li)abs(a[0] - b[var1]) + abs(a[n - 1] - b[var2]);
			
			if (var1 > 0 && var2 > 0)
				ans += abs(b[0] - a[bestCandidate(a, b[0])]);
			if (var1 < n - 1 && var2 < n - 1)
				ans += abs(b[n - 1] - a[bestCandidate(a, b[n - 1])]);
			
			bst = min(bst, ans);
		}
	}
	cout << bst << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while (t--) {
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> a(n);
    for (auto &[x, y] : a) scanf("%d %d", &x, &y);
    
    set<pair<int, int>> st(a.begin(), a.end());
    map<pair<int, int>, pair<int, int>> ans;
    queue<pair<int, int>> q;
    for (auto [x, y] : a) {
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (st.count({nx, ny})) {
                continue;
            }
            ans[{x, y}] = {nx, ny};
            q.push({x, y});
            break;
        }
    }
    
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!st.count({nx, ny}) || ans.count({nx, ny})) {
                continue;
            }
            ans[{nx, ny}] = ans[{x, y}];
            q.push({nx, ny});
        }
    }
    
    for (auto [x, y] : a) {
        auto it = ans[{x, y}];
        printf("%d %d\n", it.first, it.second);
    }
    
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 3043;

vector<int> g[2 * N];
int n;
int used[2 * N];

int choose2(int n)
{
    return n * (n + 1) / 2;
}

int count_ways(int L, int R, const vector<int>& forbidden)
{
    if(L > R)
    {
        int ml = *min_element(forbidden.begin(), forbidden.end());
        int mr = *max_element(forbidden.begin(), forbidden.end());
        return choose2(ml) + choose2(mr - ml - 1) + choose2(n - 1 - mr);
    }
    int minl = 0;
    int maxl = L;
    int minr = R;
    int maxr = n - 1;
    for(auto x : forbidden)
    {
        if(L <= x && x <= R)
            return 0;
        else if(x < L) minl = max(minl, x + 1);
        else maxr = min(maxr, x - 1);
    }                            
    return (maxl - minl + 1) * (maxr - minr + 1);
}

vector<int> cur;

void dfs(int x)
{
    if(used[x] == 1) return;
    used[x] = 1;
    cur.push_back(x);
    for(auto y : g[x]) dfs(y);
}

long long calc(const vector<int>& cycle)
{
    int m = cycle.size();
    int k = m / 2;
    long long ans = 0;
    for(int i = 0; i < m; i++)
    {
        int z = cycle[i];
        if(z >= n) z -= n;
        ans += choose2(n) * 1ll * (choose2(z) + 0ll + choose2(n - z - 1));
        int l = n - 1, r = 0, L = n - 1, R = 0;
        int pl = i, pr = i;
        for(int j = 0; j < k; j++)
        {
            for(auto x : vector<int>({cycle[pl], cycle[pr]}))
            {
                if(x < n)
                {
                    l = min(l, x);
                    r = max(r, x);
                }
                else
                {
                    L = min(L, x - n);
                    R = max(R, x - n);
                }
            }
            vector<int> f, F;
            pl--;
            if(pl < 0) pl += m;
            pr++;
            if(pr >= m) pr -= m;
            for(auto x : vector<int>({cycle[pl], cycle[pr]}))
            {                     
                if(x < n) f.push_back(x);
                else F.push_back(x - n);
            }
            long long add = count_ways(l, r, f) * 1ll * count_ways(L, R, F);
            ans += add;
        }
    }
    return ans;       
}

int main()
{
    cin >> n;
    for(int i = 0; i < 2 * n; i++)
    {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    long long ans = n * 1ll * choose2(n) * 1ll * choose2(n) * 2ll;
    for(int i = 0; i < n; i++)
    {
        if(used[i]) continue;
        dfs(i);
        vector<int> cycle = cur;
        ans -= calc(cycle);
        cur = vector<int>();
    }
    cout << ans / 2 << endl;
}

#include <bits/stdc++.h>

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

using namespace std;

struct node{
	node *l, *r;
	long long sumc, sumr;
	node() : l(NULL), r(NULL), sumc(0), sumr(0) {}
	node(node* l, node* r, long long sumc, long long sumr) : l(l), r(r), sumc(sumc), sumr(sumr) {}
};

node* build(int l, int r, vector<int> &c){
	if (l == r - 1)
		return new node(NULL, NULL, c[l], 0);
	int m = (l + r) / 2;
	node* nw = new node();
	nw->l = build(l, m, c);
	nw->r = build(m, r, c);
	nw->sumc = nw->l->sumc + nw->r->sumc;
	return nw;
}

node* upd(node* v, int l, int r, int pos, int val){
	if (l == r - 1)
		return new node(NULL, NULL, 0, val);
	int m = (l + r) / 2;
	node* nw = new node(v->l, v->r, 0, 0);
	if (pos < m)
		nw->l = upd(v->l, l, m, pos, val);
	else
		nw->r = upd(v->r, m, r, pos, val);
	nw->sumc = nw->l->sumc + nw->r->sumc;
	nw->sumr = nw->l->sumr + nw->r->sumr;
	return nw;
}

long long getsum(node *v, int mult){
	return v->sumc + v->sumr * mult;
}

int trav(node *v, int l, int r, int L, int R, long long &lft, int mult){
	if (L >= R){
		return 0;
	}
	if (l == L && r == R && lft - getsum(v, mult) >= 0){
		lft -= getsum(v, mult);
		return r - l;
	}
	if (l == r - 1){
		return 0;
	}
	int m = (l + r) / 2;
	int cnt = trav(v->l, l, m, L, min(m, R), lft, mult);
	if (cnt == max(0, min(m, R) - L))
		cnt += trav(v->r, m, r, max(m, L), R, lft, mult);
	return cnt;
}

struct seg{
	int l, r, lst, cur;
};

int main() {
	int n;
	scanf("%d", &n);
	vector<int> c(n), r(n);
	forn(i, n) scanf("%d%d", &c[i], &r[i]);
	
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int x, int y){
		return c[x] / r[x] > c[y] / r[y];
	});
	vector<int> vals;
	for (int i : ord) vals.push_back(c[i] / r[i]);
	
	vector<node*> root(1, build(0, n, c));
	for (int i : ord)
		root.push_back(upd(root.back(), 0, n, i, r[i]));
	
	vector<seg> st;
	for (int i = n - 1; i >= 0; --i)
		st.push_back({i, i + 1, 0, c[i]});
	
	long long ans = 0;
	int q;
	scanf("%d", &q);
	forn(_, q){
		int t;
		long long h;
		scanf("%d%lld", &t, &h);
		while (!st.empty()){
			auto it = st.back();
			st.pop_back();
			if (it.r - it.l == 1){
				it.cur = min((long long)c[it.l], it.cur + (t - it.lst) * 1ll * r[it.l]);
				if (it.cur <= h){
					h -= it.cur;
				}
				else{
					st.push_back({it.l, it.r, t, int(it.cur - h)});
					h = 0;
				}
			}
			else{
				int mx = vals.rend() - lower_bound(vals.rbegin(), vals.rend(), t - it.lst);
				int res = it.l + trav(root[mx], 0, n, it.l, it.r, h, t - it.lst);
				assert(res <= it.r);
				if (res != it.r){
					if (it.r - res > 1)
						st.push_back({res + 1, it.r, it.lst, 0});
					int nw = min((long long)c[res], r[res] * 1ll * (t - it.lst));
					assert(nw - h > 0);
					st.push_back({res, res + 1, t, int(nw - h)});
					h = 0;
				}
			}
			if (h == 0){
				break;
			}
		}
		if (st.empty()){
			st.push_back({0, n, t, 0});
		}
		else if (st.back().l != 0){
			st.push_back({0, st.back().l, t, 0});
		}
		ans += h;
	}
	
	printf("%lld\n", ans);
	return 0;
}

for _ in range(int(input())):
	s = input()
	for (d, k) in zip("RGB", "rgb"):
		if s.find(d) < s.find(k):
			print("NO")
			break
	else:
		print("YES")

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; ++i) {
			cout << i;
			for (int j = n; j > 0; --j) if (i != j)
				cout << ' ' << j;
			cout << '\n';
		}
	}
}

INF = 10**9

for _ in range(int(input())):
	n, x = map(int, input().split())
	a = list(map(int, input().split()))
	mx = [-INF for i in range(n + 1)]
	mx[0] = 0
	for l in range(n):
		s = 0
		for r in range(l, n):
			s += a[r]
			mx[r - l + 1] = max(mx[r - l + 1], s)
	ans = [0 for i in range(n + 1)]
	for k in range(n + 1):
		bst = 0
		for i in range(n + 1):
			bst = max(bst, mx[i] + min(k, i) * x)
		ans[k] = bst
	print(" ".join([str(x) for x in ans]))

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = 998244353;

int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n, m, k, q;
		scanf("%d%d%d%d", &n, &m, &k, &q);
		vector<int> xs(q), ys(q);
		forn(i, q) scanf("%d%d", &xs[i], &ys[i]);
		int ans = 1;
		set<int> ux, uy;
		for (int i = q - 1; i >= 0; --i){
			bool fl = false;
			if (!ux.count(xs[i])){
				ux.insert(xs[i]);
				fl = true;
			}
			if (!uy.count(ys[i])){
				uy.insert(ys[i]);
				fl = true;
			}
			if (fl){
				ans = ans * 1ll * k % MOD;
			}
			if (int(ux.size()) == n || int(uy.size()) == m){
				break;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

from sys import stdin, stdout

MOD = 998244353

ux = []
uy = []
for _ in range(int(stdin.readline())):
	n, m, k, q = map(int, stdin.readline().split())
	while len(ux) < n:
		ux.append(False)
	while len(uy) < m:
		uy.append(False)
	xs = [-1 for i in range(q)]
	ys = [-1 for i in range(q)]
	for i in range(q):
		x, y = map(int, stdin.readline().split())
		xs[i] = x - 1
		ys[i] = y - 1
	cx = 0
	cy = 0
	ans = 1
	for i in range(q - 1, -1, -1):
		fl = False
		if not ux[xs[i]]:
			ux[xs[i]] = True
			cx += 1
			fl = True
		if not uy[ys[i]]:
			uy[ys[i]] = True
			cy += 1
			fl = True
		if fl:
			ans = ans * k % MOD
		if cx == n or cy == m:
			break
	for i in range(q):
		ux[xs[i]] = False
		uy[ys[i]] = False
	stdout.write(str(ans) + "\n")

def calc(s, n):
	ld = s.find('R')
	res = ld * (n - 1)
	y = 0
	for i in range(len(s) - 1, ld - 1, -1):
		if s[i] == 'D':
			res += y
		else:
			y += 1
	return res

for _ in range(int(input())):
	n = int(input())
	s = input()
	if s.count(s[0]) == len(s):
		print(n)
		continue
	ans = n * n
	ans -= calc(s, n)
	ans -= calc(''.join(['D' if c == 'R' else 'R' for c in s]), n)
	print(ans)

for _ in range(int(input())):
  print(''.join(sorted(input())))

for _ in range(int(input())):
  x = [ord(c) - ord('0') for c in input()]
  n = len(x)
  for i in range(n - 2, -1, -1):
    if x[i] + x[i + 1] >= 10:
      x[i + 1] += x[i] - 10
      x[i] = 1
      break
  else:
    x[1] += x[0]
    x.pop(0)
  print(''.join([chr(c + ord('0')) for c in x]))

for _ in range(int(input())):
  n = int(input())
  k = list(map(int, input().split()))
  h = list(map(int, input().split()))
  st = []
  for i in range(n):
    st.append([k[i] - h[i], k[i]])
  st.sort()
  l, r = -1, -1
  ans = 0
  for it in st:
    if it[0] >= r:
      ans += (r - l) * (r - l + 1) // 2
      l, r = it
    else:
      r = max(r, it[1])
  ans += (r - l) * (r - l + 1) // 2
  print(ans)

calc = 1
nxt = [1, 0]

for _ in range(int(input())):
  n = int(input())
  a = sorted(list(map(int, input().split())))
  while calc <= n:
    for i in range(calc):
      nxt.append(calc - i - 1)
    calc *= 2
  left = []
  for i in range(n + 1):
    if i == 0 or i == n or a[i] != a[i - 1]:
      left.append(i)
    else:
      left.append(left[-1])
  mid = 1
  ans = n + 2
  while mid <= n:
    for len1 in range(n + 1):
      if left[len1] == len1:
        len2 = left[min(n, len1 + mid)] - len1
        len3 = n - len1 - len2
        ans = min(ans, nxt[len1] + (mid - len2) + nxt[len3])
    mid *= 2
  print(ans)

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;

vector<int> g[N];
int cnt[N];
int c[N];
vector<int> g2[N];
int par[N];
int used[N];

void dfs(int x, int p = -1)
{
    par[x] = p;
    for(auto y : g[x])
        if(y != p)
        {
            dfs(y, x);
            cnt[x] += cnt[y];
        }
    cnt[x] += c[x];
}   

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &c[i]);
    for(int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(0);
    for(int i = 0; i < n; i++)
        for(auto j : g[i])
        {
            if(i == par[j])
            {
                if(c[i] == 1 || cnt[0] - cnt[j] > 1)
                    g2[i].push_back(j);
            }
            else
            {
                if(c[i] == 1 || cnt[i] > 1)
                    g2[i].push_back(j);
            }
        }
    queue<int> q;
    for(int i = 0; i < n; i++)
    {
        if(c[i] == 1)
        {
            q.push(i);
            used[i] = 1;
        }
    }
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(auto y : g2[k])
            if(used[y] == 0)
            {
                used[y] = 1;
                q.push(y);
            }
    }
    for(int i = 0; i < n; i++)
        printf("%d ", used[i]);
    puts("");
}

#include <bits/stdc++.h>     

using namespace std;

const int MOD = 998244353;
const int L = 720720;

int add(int x, int y, int m = MOD)
{
    x += y;
    if(x >= m) x -= m;
    return x;
}

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

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));
}

int main()
{
    int n, a0, x, y, k, M;
    cin >> n >> a0 >> x >> y >> k >> M;
    vector<int> arr(n);
    arr[0] = a0;
    for(int i = 1; i < n; i++)
        arr[i] = add(mul(arr[i - 1], x, M), y, M);
    int ans = 0;
    int total_ways = binpow(n, k);
    int coeff = mul(divide(total_ways, n), k);
    vector<vector<int>> dp(k, vector<int>(L));
    for(int i = 0; i < n; i++)
    {
        int p = arr[i] / L;
        int q = arr[i] % L;
        dp[0][q]++;
        ans = add(ans, mul(p, mul(L, coeff)));
    }
    int cur_coeff = divide(total_ways, n);
    for(int i = 1; i <= k; i++)
    {
        for(int j = 0; j < L; j++)
        {
            int cur = dp[i - 1][j];
            if(i < k)
                dp[i][j] = add(dp[i][j], mul(n - 1, cur));
            ans = add(ans, mul(j, mul(cur, cur_coeff)));
            if(i < k)
                dp[i][j - (j % i)] = add(dp[i][j - (j % i)], cur);
        }
        cur_coeff = divide(cur_coeff, n);
    }
    cout << ans << endl;        
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    vector<int> l(3);
    for (int i = 0; i < 3; ++i)
      cin >> l[i];
    bool ok = false;
    for (int i = 0; i < 3; ++i)
      ok |= l[i] == l[(i + 1) % 3] + l[(i + 2) % 3];
    for (int i = 0; i < 3; ++i) if (l[i] % 2 == 0)
      ok |= l[(i + 1) % 3] == l[(i + 2) % 3];
    cout << (ok ? "YES\n" : "NO\n");
  }
} 

for _ in range(int(input())):
	n = int(input())
	p = [int(x) for x in input().split()]
	s = input()
	l = sorted([[s[i], p[i], i] for i in range(n)])
	q = [-1 for i in range(n)]
	for i in range(n):
		q[l[i][2]] = i + 1
	print(*q)

#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;

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

int n;
li k;
vector<int> a;

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	a.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	return true;
}

li accurateFloor(li a, li b) {
	li val = a / b;
	while (val * b > a)
		val--;
	return val;
}

inline void solve() {
	sort(a.begin(), a.end());
	vector<li> pSum(n + 1, 0);
	fore (i, 0, n)
		pSum[i + 1] = pSum[i] + a[i];
	
	li ans = 1e18;
	fore (y, 0, n) {
		//(a[0] - x)(y + 1) + (pSum[n - y] - a[0]) <= k
		//a[0] - x <= (k - pSum[n - y] + a[0]) / (y + 1)
		//x == a[0] - (k - pSum[n - y] + a[0]) / (y + 1)
		
		li x = a[0] - accurateFloor(k - pSum[n - y] + a[0], y + 1);
		ans = min(ans, y + max(0LL, x));
	}
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while (t--) {
		read();
		solve();
	}
	return 0;
}

#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 main()
{
    int n;
    cin >> n;
    int k;
    cin >> k;
    string s;
    cin >> s;
    vector<int> p(n + 1);
    for(int i = 0; i < n; i++) p[i + 1] = p[i] + (s[i] - '0');
    vector<vector<int>> C(n + 1);
    for(int i = 0; i <= n; i++)
    {
        C[i].resize(i + 1);
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++)
            C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    }
    int ans = 1;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
        {
            int cnt = j + 1 - i;
            int cnt1 = p[j + 1] - p[i];
            if(cnt1 > k || p[n] < k) continue;
            cnt -= 2;
            if(s[i] == '0') cnt1--;
            if(s[j] == '0') cnt1--;
            if(cnt1 <= cnt && cnt1 >= 0 && cnt >= 0)
                ans = add(ans, C[cnt][cnt1]);
        }
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> x(n);
    forn(i, n) scanf("%d", &x[i]);
    vector<vector<int>> a(n, vector<int>(m));
    forn(i, n) forn(j, m) scanf("%1d", &a[i][j]);
    
    int ans = -1;
    vector<int> best;
    forn(mask, 1 << n) {
      vector<int> val(m);
      forn(i, n) forn(j, m) if (a[i][j]) val[j] += ((mask >> i) & 1) ? +1 : -1;
      int res = 0;
      forn(i, n) res += ((mask >> i) & 1) ? -x[i] : x[i];
      vector<int> p(m);
      iota(p.begin(), p.end(), 0);
      sort(p.begin(), p.end(), [&](int x, int y) { return val[x] < val[y]; });
      forn(i, m) res += val[p[i]] * (i + 1);
      if (res > ans) ans = res, best = p;
    }
    
    vector<int> ansPerm(m);
    forn(i, m) ansPerm[best[i]] = i;
    forn(i, m) printf("%d ", ansPerm[i] + 1);
    puts("");
  }
} 

#include <bits/stdc++.h>

using namespace std;

const int N = 1000 * 1000 + 13;

using li = unsigned long long;

int pr[N];
li hs[N], f[N];
unordered_map<li, int> rf;

int main() {
  int n;
  scanf("%d", &n);
  
  mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
  iota(pr, pr + N, 0);
  for (int i = 2; i <= n; ++i) if (pr[i] == i) {
    for (int j = i; j <= n; j += i) pr[j] = min(pr[j], i);
    hs[i] = rnd();
  }
  for (int i = 2; i <= n; ++i) {
    f[i] = f[i - 1];
    int x = i;
    while (x != 1) {
      f[i] ^= hs[pr[x]];
      x /= pr[x];
    }
    rf[f[i]] = i;
  }
  
  auto solve = [&] (int n) -> vector<int> {
    li fp = 0;
    for (int i = 2; i <= n; ++i) fp ^= f[i];
    if (fp == 0) return {};
    if (rf.count(fp)) return {rf[fp]};
    for (int i = 2; i <= n; ++i) {
        li x = f[i] ^ fp;
        if (rf.count(x) && rf[x] != i) return {rf[x], i};
    }
    return {2, n / 2, n};
  };
  
  auto ans = solve(n);
  printf("%d\n", n - (int)ans.size());
  for (int i = 1; i <= n; ++i)
    if (find(ans.begin(), ans.end(), i) == ans.end()) printf("%d ", i);
  puts("");
} 

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    cout << (count(s.begin(), s.end(), 'N') == 1 ? "NO\n" : "YES\n");
  }
} 

for _ in range(int(input())):
  w, h = map(int, input().split())
  ans = 0
  for i in range(4):
    a = [int(x) for x in input().split()][1:]
    ans = max(ans, (a[-1] - a[0]) * (h if i < 2 else w))
  print(ans)

for _ in range(int(input())):
  n, k, x = map(int, input().split())
  x -= 1
  s = input()[::-1]
  res = []
  i = 0
  while i < n:
    if s[i] == 'a':
      res.append(s[i])
    else:
      j = i
      while j + 1 < n and s[j + 1] == s[i]:
        j += 1
      cur = (j - i + 1) * k + 1
      res.append('b' * (x % cur))
      x //= cur
      i = j
    i += 1
  print(''.join(res[::-1]))

#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())

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
  return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
  fore(i, 0, sz(v)) {
    if(i) out << " ";
    out << v[i];
  }
  return out;
}

int n;
vector<int> a;

inline bool read() {
  if(!(cin >> n))
    return false;
  a.resize(n);
  fore (i, 0, n)
    cin >> a[i];
  return true;
}

bool p(int val, int c1, int c2, int c3) {
  fore (cur1, 0, c1 + 1) fore (cur2, 0, c2 + 1) {
    if (cur1 + 2 * cur2 > val)
      continue;
    if ((val - cur1 - 2 * cur2) % 3 != 0)
      continue;
    if ((val - cur1 - 2 * cur2) / 3 <= c3)
      return true;
  }
  return false;
}

bool possible(int c1, int c2, int c3) {
  for (int v : a) {
    if (!p(v, c1, c2, c3))
      return false;
  }
  return true;
}

inline void solve() {
  int m = *max_element(a.begin(), a.end());
  int ans = int(1e9);
  
  const int MAG = 3;
  fore (c1, 0, MAG) fore (c2, 0, MAG) {
    int c3 = max(0, (m - c1 - 2 * c2 + 2) / 3);
    assert(c1 + 2 * c2 + 3 * c3 >= m);
    
    if (possible(c1, c2, c3))
      ans = min(ans, c1 + c2 + c3);
  }
  cout << ans << endl;
}

int main() {
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
#endif
  int t; cin >> t;
  while(t--) {
    read();
    solve();
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 500 * 1000 + 13;

int main() {
  int q;
  scanf("%d", &q);
  vector<int> t(q), x(q), y(q);
  for (int i = 0; i < q; ++i) {
    scanf("%d%d", &t[i], &x[i]);
    if (t[i] == 2) scanf("%d", &y[i]);
  }
  vector<int> p(N);
  iota(p.begin(), p.end(), 0);
  vector<int> ans;
  for (int i = q - 1; i >= 0; --i) {
    if (t[i] == 1) {
      ans.push_back(p[x[i]]);
    } else {
      p[x[i]] = p[y[i]];
    }
  }
  reverse(ans.begin(), ans.end());
  for (int &x : ans) printf("%d ", x);
} 

#include <bits/stdc++.h>

using namespace std;

const int N = 500 * 1000 + 13;

int n, q;
vector<int> pos[N];

int main() {
  scanf("%d", &q);
  while (q--) {
    int t, x, y;
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d", &x);
      pos[x].push_back(n++);
    } else {
      scanf("%d%d", &x, &y);
      if (x != y) {
        if (pos[x].size() > pos[y].size()) pos[x].swap(pos[y]);
        for (int &i : pos[x]) pos[y].push_back(i);
        pos[x].clear();
      }
    }
  }
  vector<int> ans(n);
  for (int x = 0; x < N; ++x)
    for (int &i : pos[x]) 
      ans[i] = x;
  for (int &x : ans) printf("%d ", x);
} 

#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;
const int N = 1000 * 1000 + 13;

int n;
int p[N], a[N];
int dp[N][2][2];
pair<int, int> pr[N][2][2];

void solve() {
  scanf("%d", &n);
  forn(i, n) scanf("%d", &p[i]);
  forn(i, n) forn(pos, 2) forn(sg, 2)
    dp[i][pos][sg] = INF;
  dp[0][0][0] = dp[0][0][1] = -INF;
  
  forn(i, n - 1) forn(pos, 2) forn(sg, 2) if (dp[i][pos][sg] != INF) {
    forn(nsg, 2) {
      int x = sg ? -p[i] : p[i];
      int y = dp[i][pos][sg];
      if (pos) swap(x, y);
      int z = nsg ? -p[i + 1] : p[i + 1];
      if (z > x) {
        if (dp[i + 1][0][nsg] > y) {
          dp[i + 1][0][nsg] = y;
          pr[i + 1][0][nsg] = make_pair(pos, sg);
        }
      } else if (z > y)  {
        if (dp[i + 1][1][nsg] > x) {
          dp[i + 1][1][nsg] = x;
          pr[i + 1][1][nsg] = make_pair(pos, sg);
        }
      }
    }
  }
  
  int pos = -1, sg = -1;
  forn(j, 2) forn(k, 2) if (dp[n - 1][j][k] != INF) 
    pos = j, sg = k;
  if (pos == -1) {
    puts("NO");
    return;
  }
  for (int i = n - 1; i >= 0; i--) {
    a[i] = sg ? -p[i] : p[i];
    tie(pos, sg) = pr[i][pos][sg];
  }
  
  puts("YES");
  forn(i, n) printf("%d ", a[i]);
  puts("");
}

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

#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;
const int N = 1000 * 1000 + 13;

int n;
int p[N], a[N];
int dp[N][2], pr[N][2];

void solve() {
  scanf("%d", &n);
  forn(i, n) scanf("%d", &p[i]);
  forn(i, n) forn(j, 2) dp[i][j] = INF;
  dp[0][0] = dp[0][1] = -INF;
  forn(i, n - 1) forn(j, 2) if (dp[i][j] != INF) {
    int x = j ? -p[i] : p[i];
    int y = dp[i][j];
    if (x < y) swap(x, y);
    forn(nj, 2) {
      int z = nj ? -p[i + 1] : p[i + 1];
      if (z > x) {
        if (dp[i + 1][nj] > y) {
          dp[i + 1][nj] = y;
          pr[i + 1][nj] = j;
        }
      } else if (z > y)  {
        if (dp[i + 1][nj] > x) {
          dp[i + 1][nj] = x;
          pr[i + 1][nj] = j;
        }
      }
    }
  }
  int j = -1;
  forn(i, 2) if (dp[n - 1][i] != INF) j = i;
  if (j == -1) {
    puts("NO");
    return;
  }
  for (int i = n - 1; i >= 0; i--) {
    a[i] = j ? -p[i] : p[i];
    j = pr[i][j];
  }
  puts("YES");
  forn(i, n) printf("%d ", a[i]);
  puts("");
}

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

#include<bits/stdc++.h>

using namespace std;

const int N = 23;
const int A = 26;
const int S = 20043;
int n;
string inp[N];
char buf[S];
int cnt[N][A];
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;
}

void flip_all(vector<int>& a)
{
    int msk = (1 << n) - 1;
    for(int i = 0; i < (1 << (n - 1)); i++)
        swap(a[i], a[i ^ msk]);
}

int val[S];
int* where[S];
int cur = 0;

void change(int& x, int y)
{
    where[cur] = &x;
    val[cur] = x;
    x = y;
    cur++;
}

void rollback()
{
    --cur;
    (*where[cur]) = val[cur];
}

void zeta_transform(vector<int>& a)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < (1 << n); j++)
            if((j & (1 << i)) == 0)
                a[j ^ (1 << i)] = add(a[j ^ (1 << i)], a[j]);
    }
}                     

void mobius_transform(vector<int>& a)
{
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = (1 << n) - 1; j >= 0; j--)
            if((j & (1 << i)) != 0)
                a[j] = sub(a[j], a[j ^ (1 << i)]);
    }
}

int cur_max[A];
vector<int> mask_cnt;

void rec(int depth, int mask)
{
    if(depth == n)
    {
        mask_cnt[mask] = 1;
        for(int i = 0; i < A; i++)
            mask_cnt[mask] = mul(mask_cnt[mask], cur_max[i] + 1);
    }
    else
    {
        int state = cur;
        for(int i = 0; i < A; i++)
            change(cur_max[i], min(cur_max[i], cnt[depth][i]));
        rec(depth + 1, mask + (1 << depth));
        while(state != cur) rollback();
        rec(depth + 1, mask);
    }   
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%s", buf);
        inp[i] = buf;
        for(auto x : inp[i])
            cnt[i][x - 'a']++;
    }

    for(int i = 0; i < A; i++)
        cur_max[i] = S;
    mask_cnt.resize(1 << n);
    rec(0, 0);
    flip_all(mask_cnt);
    mobius_transform(mask_cnt);
    flip_all(mask_cnt);
    int sum = 0;
    for(int i = 0; i < (1 << n); i++) sum = add(sum, mask_cnt[i]);
    zeta_transform(mask_cnt);
    vector<int> res(1 << n);
    for(int i = 0; i < (1 << n); i++)
        res[i] = sub(sum, mask_cnt[((1 << n) - 1) ^ i]);

    long long ans = 0;

    for(int i = 0; i < (1 << n); i++)
    {
        int c = 0, s = 0;
        for(int j = 0; j < n; j++)
        {
            if(i & (1 << j))
            {
                c++;
                s += j + 1;
            }   
        }
        ans ^= res[i] * 1ll * c * 1ll * s;
    }

    //for(int i = 0; i < (1 << n); i++) printf("%d\n", res[i]);
    printf("%lld\n", ans);
}