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

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
	int t;
	cin >> t;
	while (t--){
		long long x1, x2;
		int p1, p2;
		cin >> x1 >> p1 >> x2 >> p2;
		int mn = min(p1, p2);
		p1 -= mn;
		p2 -= mn;
		if (p1 >= 7)
			cout << ">" << endl;
		else if (p2 >= 7)
			cout << "<" << endl;
		else{
			for (int i = 0; i < p1; ++i) x1 *= 10;
			for (int i = 0; i < p2; ++i) x2 *= 10;
			if (x1 < x2)
				cout << "<" << endl;
			else if (x1 > x2)
				cout << ">" << endl;
			else
				cout << "=" << 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;
    int mn = *min_element(a.begin(), a.end());
    for (int i = 0, k = 0; k < n / 2; ++i) if (a[i] != mn) {
      cout << a[i] << ' ' << mn << '\n';
      k += 1;
    }
  }
}

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    li h;
    cin >> n >> h;
    vector<li> a(n);
    for (li &x : a) cin >> x;
    li l = 1, r = 1e18;
    while (l <= r) {
      li m = (l + r) / 2;
      li sum = m;
      for (int i = 0; i < n - 1; ++i) 
        sum += min(m, a[i + 1] - a[i]);
      if (sum < h) l = m + 1;
      else r = m - 1;
    }
    cout << r + 1 << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    vector<int> dp1(n + 2), dp2(n + 2);
    dp1[0] = 1;
    while (n--) {
      int x;
      scanf("%d", &x);
      dp1[x + 1] = add(dp1[x + 1], dp1[x + 1]);
      dp1[x + 1] = add(dp1[x + 1], dp1[x]);
      if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp2[x - 1]);
      if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp1[x - 1]);
      dp2[x + 1] = add(dp2[x + 1], dp2[x + 1]);
    }
    int ans = 0;
    for (int x : dp1) ans = add(ans, x);
    for (int x : dp2) ans = add(ans, x);
    printf("%d\n", add(ans, MOD - 1));
  }
} 

#include <bits/stdc++.h>

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

using namespace std;

struct cell{
	int x, y;
};

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

int main() {
	int t;
	cin >> t;
	while (t--){
		int n, m;
		cin >> n >> m;
		vector<string> s(n);
		int lx = -1, ly = -1;
		forn(i, n){
			cin >> s[i];
			forn(j, m) if (s[i][j] == 'L'){
				lx = i;
				ly = j;
			}
		}
		auto in = [&](int x, int y){
			return 0 <= x && x < n && 0 <= y && y < m;
		};
		vector<vector<int>> d(n, vector<int>(m, 0));
		forn(x, n) forn(y, m) if (s[x][y] == '.'){
			forn(i, 4){
				int nx = x + dx[i];
				int ny = y + dy[i];
				d[x][y] += in(nx, ny) && s[nx][ny] != '#';
			}
		}
		queue<cell> q;
		vector<vector<char>> used(n, vector<char>(m, 0));
		q.push({lx, ly});
		used[lx][ly] = true;
		while (!q.empty()){
			int x = q.front().x;
			int y = q.front().y;
			q.pop();
			forn(i, 4){
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (!in(nx, ny) || s[nx][ny] == '#' || used[nx][ny]) continue;
				--d[nx][ny];
				if (d[nx][ny] <= 1){
					used[nx][ny] = true;
					q.push({nx, ny});
				}
			}
		}
		forn(i, n){
			forn(j, m) if (s[i][j] == '.' && used[i][j])
				s[i][j] = '+';
			cout << s[i] << "\n";
		}
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 998244353;

struct Mint
{
  int val;

  bool operator==(const Mint& other)
  {
    return val == other.val;
  }

  Mint operator+(const Mint& other)
  {
    int res = val + other.val;
    while(res >= MOD) res -= MOD;
    while(res < 0) res += MOD;
    return Mint(res);
  }

  Mint operator-(const Mint& other)
  {
    int res = val - other.val;
    while(res >= MOD) res -= MOD;
    while(res < 0) res += MOD;
    return Mint(res);  
  }

  Mint operator*(const Mint& other)
  {
    return Mint((val * 1ll * other.val) % MOD);
  }

  Mint pow(int y)
  {
    Mint z(1);
    Mint x(val);
    while(y > 0)
    {
      if(y % 2 == 1) z = z * x;
      x = x * x;
      y /= 2;
    }
    return z;
  }

  Mint operator/(const Mint& other)
  {
    return Mint(val) * Mint(other.val).pow(MOD - 2);
  }

  Mint() {
      val = 0;
  };
  Mint(int x)
  {
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    val = x;
  };
};

ostream& operator<<(ostream& out, const Mint& x)
{
  return out << x.val;
}

const int g = 3;
const int LOGN = 19;

vector<Mint> w[LOGN];
vector<int> rv[LOGN];

void prepare() {
  Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
  forn(st, LOGN - 1) {
    w[st].assign(1 << st, 1);
    Mint bw = wb.pow(1 << (LOGN - st - 1));
    Mint cw = 1;
    forn(k, 1 << st) {
      w[st][k] = cw;
      cw = cw * bw;
    }
  }
  forn(st, LOGN) {
    rv[st].assign(1 << st, 0);
    if (st == 0) {
      rv[st][0] = 0;
      continue;
    }
    int h = (1 << (st - 1));
    forn(k, 1 << st)
      rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
  }
}

void ntt(vector<Mint> &a, bool inv) {
  int n = sz(a);
  int ln = __builtin_ctz(n);
  forn(i, n) {
    int ni = rv[ln][i];
    if (i < ni) swap(a[i], a[ni]);
  }
  forn(st, ln) {
    int len = 1 << st;
    for (int k = 0; k < n; k += (len << 1)) {
      fore(pos, k, k + len){
        Mint l = a[pos];
        Mint r = a[pos + len] * w[st][pos - k];
        a[pos] = l + r;
        a[pos + len] = l - r;
      }
    }
  }
  if (inv) {
    Mint rn = Mint(n).pow(MOD - 2);
    forn(i, n) a[i] = a[i] * rn;
    reverse(a.begin() + 1, a.end());
  }
}

vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
  int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
  a.resize(cnt);
  b.resize(cnt);
  ntt(a, false);
  ntt(b, false);
  vector<Mint> c(cnt);
  forn(i, cnt) c[i] = a[i] * b[i];
  ntt(c, true);
  return c;
}

vector<Mint> norm(vector<Mint> a)
{
  while(a.size() > 1 && a.back() == Mint(0))
    a.pop_back();
  return a;
}

const int N = 250043;
vector<int> G[N];
int d[N];

Mint fact[N * 2];
Mint rev[N * 2];

void dfs(int x, int p)
{
  if(p != x) d[p]++;
  for(auto y : G[x]) if(y != p) dfs(y, x);
}

Mint C(int n, int k)
{
  return fact[n] * rev[k] * rev[n - k];
}

int main()
{
  prepare();
  fact[0] = Mint(1);
  for(int i = 1; i < N * 2; i++) fact[i] = fact[i - 1] * i;
  for(int i = 0; i < N * 2; i++) rev[i] = Mint(1) / fact[i];
  int n;
  scanf("%d", &n);
  for(int i = 0; i < n - 1; i++)
  {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    G[x].push_back(y);
    G[y].push_back(x);  
  }
  dfs(0, 0);
  vector<vector<Mint>> cur;
  for(int i = 0; i < n; i++)
    if(d[i] > 0)
      cur.push_back(vector<Mint>({Mint(1), Mint(d[i])}));
  while(cur.size() > 1)
  {
    vector<vector<Mint>> ncur;
    for(int i = 0; i + 1 < cur.size(); i += 2)
      ncur.push_back(norm(mul(cur[i], cur[i + 1])));
    if(cur.size() % 2 == 1) ncur.push_back(cur.back());
    cur = ncur;  
  }
  Mint ans = 0;
  for(int i = 0; i < cur[0].size(); i++)
  {
    if(i % 2 == 0) ans = ans + cur[0][i] * fact[n - i];
    else ans = ans - cur[0][i] * fact[n - i];
  }
  cout << ans << endl;
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        println(s.last() + s.substring(1))
    }
}

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    li n, k;
    cin >> n >> k;
    li ans = 0, cur = 1;
    while (cur < k) {
      cur *= 2;
      ++ans;
    }
    if (cur < n) ans += (n - cur + k - 1) / k;
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    k += 1;
    vector<int> a(n);
    for (int& x : a) {
      cin >> x;
      int cur = 1;
      while (x--) cur *= 10;
      x = cur;
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
      int cnt = k;
      if (i + 1 < n) cnt = min(cnt, a[i + 1] / a[i] - 1);
      res += a[i] * 1LL * cnt;
      k -= cnt;
    }
    cout << res << '\n';
  }
} 

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--){
		int n, m;
		scanf("%d%d", &n, &m);
		vector<vector<int>> a(n, vector<int>(m));
		forn(i, n) forn(j, m) scanf("%d", &a[i][j]);
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&a](int x, int y){ return a[x][0] > a[y][0]; });
		vector<vector<int>> mxl(n, vector<int>(m, -INF));
		vector<vector<int>> mnr(n, vector<int>(m, INF));
		for (int i = n - 1; i >= 0; --i) forn(j, m){
			mxl[i][j] = a[ord[i]][j];
			if (i < n - 1) mxl[i][j] = max(mxl[i][j], mxl[i + 1][j]);
			if (j > 0) mxl[i][j] = max(mxl[i][j], mxl[i][j - 1]);
		}
		for (int i = n - 1; i >= 0; --i) for (int j = m - 1; j >= 0; --j){
			mnr[i][j] = a[ord[i]][j];
			if (i < n - 1) mnr[i][j] = min(mnr[i][j], mnr[i + 1][j]);
			if (j < m - 1) mnr[i][j] = min(mnr[i][j], mnr[i][j + 1]);
		}
		vector<int> mnl(m, INF), mxr(m, -INF);
		pair<int, int> ans(-1, -1);
		forn(i, n - 1){
			forn(j, m){
				mnl[j] = min(mnl[j], a[ord[i]][j]);
				if (j > 0) mnl[j] = min(mnl[j], mnl[j - 1]);
			}
			for (int j = m - 1; j >= 0; --j){
				mxr[j] = max(mxr[j], a[ord[i]][j]);
				if (j < m - 1) mxr[j] = max(mxr[j], mxr[j + 1]);
			}
			forn(j, m - 1) if (mnl[j] > mxl[i + 1][j] && mxr[j + 1] < mnr[i + 1][j + 1]){
				ans = {i, j};
			}
		}
		if (ans.first == -1){
			puts("NO");
			continue;
		}
		puts("YES");
		string res(n, '.');
		forn(i, n) res[ord[i]] = i <= ans.first ? 'R' : 'B';
		printf("%s %d\n", res.c_str(), ans.second + 1);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 505;
const int MOD = 998244353;

int n, x;
int c[N][N], dp[N][N];

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

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

int main() {
  cin >> n >> x;
  for (int i = 0; i <= n; ++i) {
    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[n][0] = 1;
  for (int i = n; i > 1; i--) {
    for (int j = 0; j < x; ++j) {
      if (!dp[i][j]) continue;
      int pw = 1, nj = min(x, j + i - 1);
      for (int k = i; k >= 0; k--) {
        dp[k][nj] = add(dp[k][nj], mul(dp[i][j], mul(c[i][k], pw)));
        pw = mul(pw, nj - j);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i <= x; ++i)
    ans = add(ans, dp[0][i]);
  cout << ans << endl;
} 

#include <bits/stdc++.h>     

using namespace std;

struct Vertex
{
 	int cost;
 	int depth;
 	int idx;
 	Vertex() {};
 	Vertex(int cost, int depth, int idx) : cost(cost), depth(depth), idx(idx) {};
};

bool operator <(const Vertex& a, const Vertex& b)
{
 	if(a.cost != b.cost)
 		return a.cost > b.cost;
 	if(a.depth != b.depth)
 		return a.depth > b.depth;
 	return a.idx < b.idx;
}

struct DSU
{
	int n;
 	vector<int> p;
 	vector<int> top;

 	int get(int x)
 	{
 		if(p[x] == x)
 			return x;
 		return p[x] = get(p[x]); 	
 	}

 	int get_top(int x)
 	{
 	 	return top[get(x)];
 	}

 	void merge(int x, int par)
 	{
 	 	p[x] = par;
 	}

 	DSU(int k = 0)
 	{
 	 	n = k;
 	 	p.resize(n);
 	 	iota(p.begin(), p.end(), 0);
 	 	top = p;
 	};
};

const int N = 200043;

int n;
vector<int> g[N];
int p[N], d[N], tin[N], tout[N];
int qv[N];
int qk[N];
int T = 0;

void dfs(int v = 0, int par = -1)
{
 	tin[v] = T++;
 	p[v] = par;
 	if(par == -1)
 		d[v] = 0;
 	else
 		d[v] = d[par] + 1;
 	for(auto x : g[v])
 		if(x != par)
 			dfs(x, v);
 	tout[v] = T;
}

pair<long long, long long> tree[4 * N];

pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
 	return make_pair(a.first + b.first, a.second + b.second);
}

pair<long long, long long> get(int v, int l, int r, int L, int R)
{
 	if(L >= R) return {0, 0};
 	if(l == L && r == R) return tree[v];
 	int m = (l + r) / 2;
 	return get(v * 2 + 1, l, m, L, min(R, m)) + get(v * 2 + 2, m, r, max(m, L), R);
}

void add(int v, int l, int r, int pos, pair<long long, long long> val)
{
 	if(l == r - 1)
 		tree[v] = tree[v] + val;
 	else
 	{
 	 	int m = (l + r) / 2;
 	 	if(pos < m) add(v * 2 + 1, l, m, pos, val);
 	 	else add(v * 2 + 2, m, r, pos, val);
 	 	tree[v] = tree[v] + val;
 	}                                                                  
}

pair<long long, long long> get_vertex_value(int v)
{
 	return get(0, 0, n, tin[v], tout[v]);
}

void add_on_path(int x, int y, pair<long long, long long> val)
{
 	// x is a descendant of y
 	add(0, 0, n, tin[x], val);
 	if(p[y] != -1)
 		add(0, 0, n, tin[p[y]], make_pair(-val.first, -val.second));
}

int calculate_cost(int v, int correction)
{
	//cerr << v << " " << correction << endl;
 	pair<long long, long long> res = get_vertex_value(v);
 	// first - (second + 1) * k <= 0
 	long long k = (res.first + res.second) / (res.second + 1) - 1;
 	if(correction < k) return correction;
 	return k;
}

int main()
{
	scanf("%d", &n);
	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);
	}
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
	 	scanf("%d %d", &qv[i], &qk[i]);
	 	--qv[i];
	}                   

	dfs();
	DSU dsu(n);
                        
	vector<long long> ans(q);
	set<Vertex> pq;
	vector<Vertex> curv(n);
	for(int i = 0; i < n; i++)
	{                     
	 	int count_children = g[i].size();
	 	if(i != 0) count_children--;               
	 	add_on_path(i, i, make_pair((long long)(count_children), 0ll)); 
	 	if(i != 0)
	 	{
	 		curv[i] = Vertex(calculate_cost(i, 200000), d[i], i);
			pq.insert(curv[i]);                                   
	 	}
                          
	}
                        
	for(int i = 0; i < q; i++)
		pq.insert(Vertex(qk[i], -1, i));

	while(!pq.empty())
	{
		Vertex z = *pq.begin();
		pq.erase(pq.begin());
		if(z.depth == -1)
		{
		 	auto res = get_vertex_value(qv[z.idx]);
		 	ans[z.idx] = res.first - res.second * z.cost;
	    }
	    else
	    {
	     	int v = z.idx;
	     	int pv = p[v];
	     	int newtop = dsu.get_top(pv);
	     	pair<long long, long long> val = get_vertex_value(v);
	     	val.second++;
	     	val.first--;
	     	if(newtop != 0)
	     		pq.erase(curv[newtop]);
	     	add_on_path(pv, newtop, val);
	     	if(newtop != 0)
	     		curv[newtop].cost = calculate_cost(newtop, z.cost);
	     	if(newtop != 0)
	     		pq.insert(curv[newtop]);
	     	dsu.merge(v, pv);
	    }
	}	

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

def solve():
	n = int(input())
	s1 = input()
	s2 = input()
	bad = False
	for i in range(n):
		bad |= s1[i] == '1' and s2[i] == '1'
	if bad:
		print('NO')
	else:
		print('YES')

t = int(input())
for i in range(t):
	solve()

t = int(input())
for i in range(t):
    n = int(input())
    a = [[] for i in range(n)]
    for j in range(n):
        a[j] = list(map(int, input().split()))
    ans = False
    for j in range(5):
        for k in range(5):
            if k != j:
                cnt1 = 0
                cnt2 = 0
                cntno = 0
                for z in range(n):
                    if a[z][j] == 1:
                        cnt1 += 1
                    if a[z][k] == 1:
                        cnt2 += 1
                    if a[z][j] == 0 and a[z][k] == 0:
                        cntno += 1
                if cnt1 >= n // 2 and cnt2 >= n // 2 and cntno == 0:
                    ans = True
    if ans:
        print('YES')
    else:
        print('NO')

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    map<int, int> cnt;
    for (auto &x : a) {
      scanf("%d", &x);
      cnt[x] += 1;
    }
    long long sum = accumulate(a.begin(), a.end(), 0LL);
    if ((2 * sum) % n != 0) {
      puts("0");
      continue;
    }
    long long need = (2 * sum) / n;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
      int a1 = a[i];
      int a2 = need - a1;
      if (cnt.count(a2)) ans += cnt[a2];
      if (a1 == a2) ans -= 1;
    }
    printf("%lld\n", ans / 2);
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n), ca(n + 1), cb(n + 1);
    for (int i = 0; i < n; ++i) {
      cin >> a[i] >> b[i];
      ca[a[i]]++; cb[b[i]]++;
    }
    long long ans = n * 1LL * (n - 1) * (n - 2) / 6;
    for (int i = 0; i < n; ++i) 
      ans -= (ca[a[i]] - 1) * 1LL * (cb[b[i]] - 1);
    cout << ans << '\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, q;
	scanf("%d%d%d", &n, &m, &q);
	vector<vector<int>> a(n, vector<int>(m, 1));
	long long ans = 0;
	forn(x, n) forn(y, m){
		if (x == 0){
			for (int k = 1;; ++k){
				int nx = x + k / 2;
				int ny = y + (k + 1) / 2;
				if (nx == n || ny == m) break;
				ans += k;
			}
		}
		if (y == 0){
			for (int k = 1;; ++k){
				int nx = x + (k + 1) / 2;
				int ny = y + k / 2;
				if (nx == n || ny == m) break;
				ans += k;
			}
		}
	}
	ans += n * m;
	forn(i, q){
		int x, y;
		scanf("%d%d", &x, &y);
		--x, --y;
		forn(c, 2){
			int l = 1, r = 1;
			while (true){
				int nx = x + (l + c) / 2;
				int ny = y + (l + !c) / 2;
				if (nx == n || ny == m || a[nx][ny] == 0) break;
				++l;
			}
			while (true){
				int nx = x - (r + !c) / 2;
				int ny = y - (r + c) / 2;
				if (nx < 0 || ny < 0 || a[nx][ny] == 0) break;
				++r;
			}
			if (a[x][y] == 0){
				ans += l * r;
			}
			else{
				ans -= l * r;
			}
		}
		ans += a[x][y];
		a[x][y] ^= 1;
		ans -= a[x][y];
		printf("%lld\n", ans);
	}
}

#include <bits/stdc++.h>     

using namespace std;

const int INF = int(1e9);

const int N = 20;
const int M = (1 << N);

struct BracketSeqn
{
 	int balance;
 	int lowestBalance;
 	vector<int> queryAns;

 	pair<int, bool> go(int x, bool f)
 	{
     	if(f)
     		return make_pair(0, true);
       	else
       		return make_pair(x < queryAns.size() ? queryAns[x] : 0, x + lowestBalance < 0);
    }

	BracketSeqn() {};
	BracketSeqn(string s)
	{
		vector<int> bal;
		int cur = 0;
		int n = s.size();
		for(auto x : s)
		{
		 	if(x == '(')
		 		cur++;
		 	else	
		 		cur--;
		 	bal.push_back(cur);	
		}
		balance = bal.back();
		lowestBalance = min(0, *min_element(bal.begin(), bal.end()));
		vector<vector<int>> negPos(-lowestBalance + 1);
		for(int i = 0; i < n; i++)
		{
		 	if(bal[i] > 0) continue;
		 	negPos[-bal[i]].push_back(i);
		}
		queryAns.resize(-lowestBalance + 1);
		for(int i = 0; i < queryAns.size(); i++)
		{
		 	int lastPos = int(1e9);
		 	if(i != -lowestBalance)
		 		lastPos = negPos[i + 1][0];
		 	queryAns[i] = lower_bound(negPos[i].begin(), negPos[i].end(), lastPos) - negPos[i].begin();
		}
	};
};

int dp[M][2];
char buf[M];
int total_bal[M];

int main()
{
	int n;
	scanf("%d", &n);
	vector<BracketSeqn> bs;
	for(int i = 0; i < n; i++)
	{
	 	scanf("%s", buf);
	 	string s = buf;
	 	bs.push_back(BracketSeqn(s));
	}
	for(int i = 0; i < (1 << n); i++)               
	 	for(int j = 0; j < n; j++)
	 		if(i & (1 << j))
	 			total_bal[i] += bs[j].balance;
	for(int i = 0; i < (1 << n); i++)
		for(int j = 0; j < 2; j++)
			dp[i][j] = -int(1e9);
	dp[0][0] = 0;
	for(int i = 0; i < (1 << n); i++)
		for(int f = 0; f < 2; f++)
		{
		 	if(dp[i][f] < 0) continue;
		 	for(int k = 0; k < n; k++)
		 	{
		 	 	if(i & (1 << k)) continue;
		 	 	pair<int, bool> res = bs[k].go(total_bal[i], f);
		 	 	dp[i ^ (1 << k)][res.second] = max(dp[i ^ (1 << k)][res.second], dp[i][f] + res.first);
		 	}
		}
	printf("%d\n", max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1]));
}

#include <bits/stdc++.h>

using namespace std;

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

const int MOD[] = { 597804841, 618557587, 998244353 };
const int N = 500 * 1000 + 13;
const int K = 3;

using hs = array<int, K>;

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

int mul(int x, int y, int mod) {
  return x * 1LL * y % mod;
}

hs get(const int& x) {
  hs c;
  forn(i, K) c[i] = x;
  return c;
}

hs operator +(const hs& a, const hs& b) { 
  hs c;
  forn(i, K) c[i] = add(a[i], b[i], MOD[i]);
  return c;
}

hs operator -(const hs& a, const hs& b) {
  hs c;
  forn(i, K) c[i] = add(a[i], -b[i], MOD[i]);
  return c; 
}

hs operator *(const hs& a, const hs& b) {
  hs c;
  forn(i, K) c[i] = mul(a[i], b[i], MOD[i]);
  return c; 
}

int n, m;
string s, sx;
hs sum[N], pw[N];

hs get(int l, int r) {
  return sum[r] - sum[l] * pw[r - l];
}

vector<int> zfunction(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(z[i - l], r - i + 1);
    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() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  
  cin >> s >> sx;
  n = s.size();
  m = sx.size();
  
  pw[0] = get(1);
  forn(i, N - 1) pw[i + 1] = pw[i] * get(10); 
  sum[0] = get(0);
  forn(i, n) sum[i + 1] = sum[i] * get(10) + get(s[i] - '0'); 
  hs x = get(0);
  forn(i, m) x = x * get(10) + get(sx[i] - '0');
  
  if (m > 1) for (int i = 0; i + 2 * (m - 1) <= n; ++i) {
    if (get(i, i + m - 1) + get(i + m - 1, i + 2 * (m - 1)) == x) {
      cout << i + 1 << ' ' << i + m - 1 << '\n';
      cout << i + m << ' ' << i + 2 * (m - 1) << '\n';
      return 0;
    }
  }
  
  auto z = zfunction(sx + "#" + s);
  
  for (int i = 0; i + m <= n; ++i) {
    int lcp = z[m + i + 1];
    for (int len = m - lcp - 1; len <= m - lcp; ++len) {
      if (len < 1) continue;
      if (i + m + len <= n && get(i, i + m) + get(i + m, i + m + len) == x) {
        cout << i + 1 << ' ' << i + m << '\n';
        cout << i + m + 1 << ' ' << i + m + len << '\n';
        return 0;
      }
      if (i >= len && get(i - len, i) + get(i, i + m) == x) {
        cout << i - len + 1 << ' ' << i << '\n';
        cout << i + 1 << ' ' << i + m << '\n';
        return 0;
      }
    }
  }
  
  assert(false);
}

t = int(input())
for i in range(t):
    n = int(input())
    for j in range(n):
        print("()" * j + "(" * (n - j) + ")" * (n - j))

for _ in range(int(input())):
	a, b, c, m = map(int, input().split())
	a, b, c = sorted([a, b, c])
	print("YES" if c - (a + b + 1) <= m <= a + b + c - 3 else "NO")

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int n;
  cin >> n;
  vector<li> a(n);
  for (auto &x : a) cin >> x;
  sort(a.begin(), a.end());
  li sum = accumulate(a.begin(), a.end(), 0LL);
  int m;
  cin >> m;
  while (m--) {
    li x, y;
    cin >> x >> y;
    int i = lower_bound(a.begin(), a.end(), x) - a.begin();
    li ans = 2e18;
    if (i > 0) ans = min(ans, (x - a[i - 1]) + max(0LL, y - sum + a[i - 1]));
    if (i < n) ans = min(ans, max(0LL, y - sum + a[i]));
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

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

using namespace std;

int n;
vector<vector<int>> a;
int m;
vector<vector<int>> b;

int main() {
	scanf("%d", &n);
	a.resize(n);
	forn(i, n){
		int c;
		scanf("%d", &c);
		a[i].resize(c);
		forn(j, c) scanf("%d", &a[i][j]);
	}
	scanf("%d", &m);
	b.resize(m);
	forn(i, m){
		b[i].resize(n);
		forn(j, n){
			scanf("%d", &b[i][j]);
			--b[i][j];
		}
	}
	sort(b.begin(), b.end());
	vector<int> ult(n);
	forn(i, n) ult[i] = int(a[i].size()) - 1;
	if (!binary_search(b.begin(), b.end(), ult)){
		forn(i, n) printf("%d ", ult[i] + 1);
		puts("");
		return 0;
	}
	int mx = 0;
	vector<int> ans(n, -1);
	forn(i, m){
		vector<int> tmp = b[i];
		int sum = 0;
		forn(j, n) sum += a[j][tmp[j]];
		forn(j, n) if (tmp[j] != 0){
			--tmp[j];
			if (!binary_search(b.begin(), b.end(), tmp) && sum - a[j][tmp[j] + 1] + a[j][tmp[j]] > mx){
				mx = sum - a[j][tmp[j] + 1] + a[j][tmp[j]];
				ans = tmp;
			}
			++tmp[j];
		}
	}
	forn(i, n){
		printf("%d ", ans[i] + 1);
	}
	puts("");
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 1'000'009;

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

int n, m, k;
map <pair <int, int>, char> c;
int cntr[N][2], cntc[N][2];
int cntx[2];
set <int> badr, badc;
set<int> ur, uc;
int p2[N];

void upd2(int pos, int col, int add, int cnt[N][2], set <int> &bad, set<int> &u) {
    cnt[pos][col] += add;
    assert(cnt[pos][col] >= 0);
    
    if (cnt[pos][0] > 0 && cnt[pos][1] > 0){
        if (!bad.count(pos))
            bad.insert(pos);
    } else {
        if (bad.count(pos))
            bad.erase(pos);
    }
    
    if (cnt[pos][0] > 0 || cnt[pos][1] > 0){
        if (!u.count(pos))
            u.insert(pos);
    } else {
        if (u.count(pos))
            u.erase(pos);
    }
}

void upd(int x, int y, int t) {
    int col = (x & 1) ^ (y & 1);
    if (c.count({x, y})) {
        int ncol = col ^ c[{x, y}];
        --cntx[ncol];
        upd2(x, ncol, -1, cntr, badr, ur);
        upd2(y, ncol, -1, cntc, badc, uc);
        c.erase({x, y});
    }
    
    if (t == -1)
        return;
        
    int ncol = col ^ t;
    ++cntx[ncol];
    upd2(x, ncol, 1, cntr, badr, ur);
    upd2(y, ncol, 1, cntc, badc, uc);
    c[{x, y}] = t;
}

int main(){
    p2[0] = 1;
    for (int i = 1; i < N; ++i)
        p2[i] = sum(p2[i - 1], p2[i - 1]);
        
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; ++i) {
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        --x, --y;
        upd(x, y, t);
        
        int res = 0;
        if(badr.size() > 0 && badc.size() > 0) {
            res = 0;
        } else if (badr.size() > 0) {
            assert(m - uc.size() >= 0);
            res = p2[m - uc.size()];
        } else if (badc.size() > 0) {
            assert(n - ur.size() >= 0);
            res = p2[n - ur.size()];
        } else {
            if (ur.size() == 0 && uc.size() == 0)
                res = sum(sum(p2[n], p2[m]), -2);
            else {
                assert(m - uc.size() >= 0);
                res = sum(res, p2[m - uc.size()]);
                assert(n - ur.size() >= 0);
                res = sum(res, p2[n - ur.size()]);
                if (cntx[0] == 0 || cntx[1] == 0) {
                    assert(cntx[0] != 0 || cntx[1] != 0);
                    res = sum(res, -1);
                }
            }
        }
        
        printf("%d\n", res);
    }
    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 mul(int x, int y)
{
 	return (x * 1ll * y) % MOD;
}

int main()
{
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	vector<vector<int>> A(n);
	vector<int> bad_num(k);
	for(int i = 0; i < n; i++)
	{
		int c;
		scanf("%d", &c);
		A[i].resize(c);
		for(int j = 0; j < c; j++)
		{
			scanf("%d", &A[i][j]); 	
			A[i][j]--;
		}
	}

	for(int i = 0; i < n; i++)
	{
	 	if(set<int>(A[i].begin(), A[i].end()).size() != A[i].size())
	 	{
	 	 	for(auto x : A[i])
	 	 		bad_num[x] = 1;
	 	}
	}
	vector<vector<int>> nxt(k);
	vector<vector<int>> prv(k);
	for(int i = 0; i < n; i++)
		for(int j = 0; j + 1 < A[i].size(); j++)
		{
		 	nxt[A[i][j]].push_back(A[i][j + 1]);
		 	prv[A[i][j + 1]].push_back(A[i][j]);
		}

	for(int i = 0; i < k; i++)
	{
	    sort(nxt[i].begin(), nxt[i].end());
	    sort(prv[i].begin(), prv[i].end());
	 	nxt[i].erase(unique(nxt[i].begin(), nxt[i].end()), nxt[i].end());
	 	prv[i].erase(unique(prv[i].begin(), prv[i].end()), prv[i].end());
	}

	vector<int> used(k, 0);
	vector<int> cnt(k + 1, 0);
	for(int i = 0; i < k; i++)
	{
		if(used[i]) continue;
	 	queue<int> q;
	 	vector<int> comp;
	 	q.push(i);
	 	used[i] = 1;
	 	while(!q.empty())
	 	{
	 		int z = q.front();
	 		q.pop();
	 		comp.push_back(z);
	 	 	for(auto x : nxt[z])
	 	 		if(!used[x])
	 	 		{
	 	 		 	used[x] = 1;
	 	 		 	q.push(x);
	 	 		}
	 	 	for(auto x : prv[z])
	 	 		if(!used[x])
	 	 		{
	 	 		 	used[x] = 1;
	 	 		 	q.push(x);
	 	 		}
	 	}
	 	bool bad = false;
	 	int cnt_beg = 0;
	 	for(auto x : comp)
	 	{
	 	 	if(prv[x].empty())
	 	 		cnt_beg++;
	 	 	if(prv[x].size() > 1 || nxt[x].size() > 1 || bad_num[x])
	 	 		bad = true;
	 	}
	 	bad |= (cnt_beg == 0);
	 	if(!bad)
	 		cnt[comp.size()]++;
	}
	vector<int> nonzero;
	for(int i = 1; i <= k; i++)
		if(cnt[i] > 0)
			nonzero.push_back(i);
	vector<int> dp(m + 1, 0);
	dp[0] = 1;
	for(int i = 1; i <= m; i++)
		for(auto x : nonzero)
		 	if(x <= i)
		 		dp[i] = add(dp[i], mul(cnt[x], dp[i - x]));

	printf("%d\n", dp[m]);
	return 0;
}

for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			print(i + 1, i + 2)
			break
	else:
		print(-1, -1)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    int n;
    string s;
    cin >> n >> s;
    vector<int> id;
    for (int i = 0; i < n; ++i) if (s[i] == '2')
      id.push_back(i);
    int k = id.size();
    if (k == 1 || k == 2) {
      cout << "NO\n";
      continue;
    }
    vector<string> t(n, string(n, '='));
    for (int i = 0; i < n; ++i) t[i][i] = 'X';
    for (int i = 0; i < k; ++i) {
      int x = id[i], y = id[(i + 1) % k];
      t[x][y] = '+';
      t[y][x] = '-';
    }
    cout << "YES\n";
    for (int i = 0; i < n; ++i) cout << t[i] << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int mx = *max_element(a.begin(), a.end());
    int cmx = count(a.begin(), a.end(), mx);
    int k = count(a.begin(), a.end(), mx - 1);
    int ans = 1, sub = 1;
    for (long long i = 1; i <= n; ++i) {
      ans = ans * i % MOD;
      if (i != k + 1) sub = sub * i % MOD;
    }
    if (cmx == 1) ans = (ans - sub + MOD) % MOD;
    cout << ans << '\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())
#define all(a) (a).begin(), (a).end()

#define x first
#define y second

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

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

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

int n, m, k;
vector<int> x, y;
vector<pt> ps;

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

inline void solve() {
	li ans = 0;
	
	fore (_i, 0, 2) {
		vector<int> cntY(m, 0);
		sort(all(ps));
		
		vector<pt> bord(k);
		
		int u = 0;
		while (u < k) {
			int v = u;
			while (v < k && ps[v].x == ps[u].x)
				v++;
			
			fore (i, u, v) {
				int r = int(lower_bound(all(y), ps[i].y) - y.begin());
				int l = r;
				if (y[l] > ps[i].y)
					l--;
				assert(y[l] <= ps[i].y && ps[i].y <= y[r]);
				
				bord[i] = {l, r};
			}
			
			fore (i, u, v) if (bord[i].x < bord[i].y)
				ans += cntY[bord[i].x];
			
			fore (i, u, v) if (bord[i].x < bord[i].y)
				cntY[bord[i].x]++;
			
			u = v;
		}
		
		
		fore (i, 0, k)
			swap(ps[i].x, ps[i].y);
		swap(x, y);
		swap(n, m);
	}
	
	cout << ans << endl;
}

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);
	
	int t; cin >> t;
	while (t--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	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 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;
}

vector<int> evaluate(int n, int choice_mask)
{
 	int cur_place = n / 2 + 1;
 	int cur_bit = n - 2;
 	vector<int> p(n);
 	vector<int> c(n);
 	for(int i = 0; i < n; i++)
 		c[i] = i;
 	while(c.size() != 1)
 	{
 		vector<int> nc;
 	 	for(int i = 0; i < c.size(); i += 2)
 	 	{
 	 	 	if(choice_mask & (1 << cur_bit))
 	 	 	{
 	 	 		p[c[i]] = cur_place;
 	 	 		nc.push_back(c[i + 1]);
 	 	 	}
 	 	 	else
 	 	 	{
 	 	 		p[c[i + 1]] = cur_place;
 	 	 		nc.push_back(c[i]);
 	 	 	}
 	 	 	cur_bit--;
 	 	}
 	 	c = nc;
 	 	cur_place /= 2;
  		cur_place++;
	}
	p[c[0]] = 1;
	return p;
}

vector<int> adjust(int n, vector<int> p, bool winning)
{
	for(int i = 0; i < n; i++)
	{
		if(p[i] == 1)
		{
		 	if(!winning) p[i]++;	
		}
		else
		 	p[i] = p[i] * 2 - 1;
	}
	return p;
}	

int get_hash(int n, vector<int> p, int A, bool partial = false, bool winning = false, int shift = 0)
{
	if(partial)
		p = adjust(n, p, winning);
 	int res = 0;
 	for(int i = 0; i < n; i++)
 		res = add(res, mul(add(i + 1, shift), binpow(A, p[i])));
 	return res;
}

int main()
{
 	int k, A, h;
 	cin >> k >> A >> h;
 	if(k <= 4)
 	{
 		for(int i = 0; i < (1 << ((1 << k) - 1)); i++)
 		{             
 			vector<int> p = evaluate(1 << k, i);
 			if(get_hash(1 << k, p, A) == h)
 			{
 		 		for(auto x : p) cout << x << " ";
 		 		cout << endl;
 		 		return 0;
 			}
 		}
 	}
 	else
 	{
 		int mask_left = -1;
 		int mask_right = -1;
 		bool left_win = false;
 		for(int c = 0; c < 2; c++)
 		{
 		 	map<int, int> left_map;
 		 	for(int i = 0; i < (1 << 16); i++)
 		 	{
 		 	 	vector<int> p = evaluate(16, i);
 		 	 	int left_hash = get_hash(16, p, A, true, c == 0, 0);
 		 	 	left_map[left_hash] = i;	
 		 	}
 		 	for(int i = 0; i < (1 << 16); i++)
 		 	{
 		 	 	vector<int> p = evaluate(16, i);
 		 	 	int right_hash = get_hash(16, p, A, true, c == 1, 16);
 		 	 	int left_hash = add(h, MOD - right_hash);
 		 	 	if(left_map.count(left_hash))
 		 	 	{
 		 	 	 	mask_left = left_map[left_hash];
 		 	 	 	mask_right = i;
 		 	 	 	left_win = (c == 0);
 		 	 	}
 		 	}
 	 	}
 	 	if(mask_left != -1)
 		{
 	 		vector<int> ans_left = evaluate(16, mask_left);
 	 		vector<int> ans_right = evaluate(16, mask_right);
 	 		ans_left = adjust(16, ans_left, left_win);
 	 		ans_right = adjust(16, ans_right, !left_win);
 	 		for(auto x : ans_left)
 	 			cout << x << " ";
 	   		for(auto x : ans_right)
 	   			cout << x << " ";
 	   		return 0;
 		}        
 	}
 	cout << -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<char>> g;
map<long long, bool> dp;

void brute(int n, vector<int> &p){
	int x = find(p.begin(), p.end(), -1) - p.begin();
	if (x == int(p.size())){
		vector<vector<char>> dp2(1 << n, vector<char>(n));
		vector<int> pos1(n), pos2(n);
		forn(i, p.size()){
			pos1[p[i]] = pos2[p[i]];
			pos2[p[i]] = i;
		}
		forn(i, n) if (g[pos1[i]][pos2[i]]) dp2[1 << i][i] = true;
		forn(mask, 1 << n) forn(i, n) if (dp2[mask][i]){
			forn(j, n) if (!((mask >> j) & 1)){
				dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos1[j]] && g[pos2[i]][pos2[j]]);
				dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos2[j]] && g[pos2[i]][pos1[j]]);
			}
		}
		forn(i, n) if (dp2[(1 << n) - 1][i]){
			long long num = 0;
			for (int x : p) num = num * 6 + x;
			dp[num] = true;
			break;
		}
		return;
	}
	for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
		p[x] = p[y] = n;
		brute(n + 1, p);
		p[x] = p[y] = -1;
	}
}

bool dfs(vector<int> p){
	vector<int> used(int(p.size()), -1);
	int cnt = 0;
	forn(i, p.size()) if (used[p[i]] == -1)
		used[p[i]] = cnt++;
	long long num = 0;
	for (int& x : p){
		x = used[x];
		num = num * 6 + x;
	}
	if (dp.count(num)) return dp[num];
	bool res = false;
	vector<int> cur(cnt);
	forn(i, p.size()) ++cur[p[i]];
	forn(i, p.size()) if (cur[p[i]] > 2){
		int x = p[i];
		for (int j = i + 1; j < int(p.size()); ++j) if (p[j] == p[i]){
			p[i] = p[j] = cnt;
			if (dfs(p)){
				res = true;
				break;
			}
			p[i] = p[j] = x;
		}
		break;
	}
	return dp[num] = res;
}

void brute2(int n, vector<int> &p){
	int x = find(p.begin(), p.end(), -1) - p.begin();
	if (x == int(p.size())){
		dfs(p);
		return;
	}
	forn(i, n + 1){
		for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
			p[x] = p[y] = i;
			brute2(max(n, i + 1), p);
			p[x] = p[y] = -1;
		}
	}
}

int main() {
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	g.resize(n, vector<char>(n));
	forn(_, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v][u] = g[u][v] = 1;
	}
	vector<int> cur(n, -1);
	brute(0, cur);
	brute2(0, cur);
	vector<long long> fact(k + 1);
	fact[0] = 1;
	for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i;
	long long ans = 0;
	for (auto it : dp) if (it.second){
		long long num = it.first;
		long long mx = 1;
		while (num){
			mx = max(mx, num % 6 + 1);
			num /= 6;
		}
		if (mx <= k){
			ans += fact[k] / fact[k - mx];
		}
	}
	printf("%lld\n", ans);
	return 0;
}