for t in range(int(input())):
	n = int(input())
	print(2 if n == 2 else (n & 1))

for t in range(int(input())):
    print('NO' if len(set(input()) & set(input())) == 0 else 'YES')

fun calc(p: IntArray, len: Int, x: Int, a: Int, y: Int, b: Int): Long {
    var ans = 0L
    var (cX, cY, cXY) = listOf(0, 0, 0)
    for (i in 1..len) {
        if (i % a == 0 && i % b == 0) cXY++
        else if (i % a == 0) cX++
        else if (i % b == 0) cY++
    }
    for (i in 0 until cXY)
        ans += p[i] * (x + y)
    for (i in 0 until cX)
        ans += p[cXY + i] * x
    for (i in 0 until cY)
        ans += p[cXY + cX + i] * y;
    return ans
}

fun main() {
    val q = readLine()!!.toInt()
    for (ct in 1..q) {
        val n = readLine()!!.toInt()
        val p = readLine()!!.split(' ').map { it.toInt() / 100 }
                .sortedDescending().toIntArray()
        var (x, a) = readLine()!!.split(' ').map { it.toInt() }
        var (y, b) = readLine()!!.split(' ').map { it.toInt() }
        val k = readLine()!!.toLong()

        if (x < y) {
            x = y.also { y = x }
            a = b.also { b = a }
        }

        var lf = 0; var rg = n + 1
        while (rg - lf > 1) {
            val mid = (lf + rg) / 2
            if (calc(p, mid, x, a, y, b) >= k)
                rg = mid
            else
                lf = mid
        }

        if (rg > n) rg = -1
        println(rg)
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;
const int INF = int(1e9) + 99;

int t, n;
int a[N];
int l[N], r[N];
int dp[N];

int main() {
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i){
			l[i] = INF;
			r[i] = -INF;
			dp[i] = 0;
		}

		vector <int> v;	
		for(int i = 0; i < n; ++i){
			scanf("%d", a + i);
			--a[i];
			v.push_back(a[i]);
			l[a[i]] = min(l[a[i]], i);
			r[a[i]] = max(r[a[i]], i);
		}

		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	
		int res = n;
		for(int i = v.size() - 1; i >= 0; --i){
			if(i + 1 == v.size() || r[v[i]] >= l[v[i + 1]]) dp[i] = 1;
			else dp[i] = 1 + dp[i + 1];
			res = min(res, int(v.size())- dp[i]);
		}

		printf("%d\n", res);
	}	

	return 0;
}                             	

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)

const int N = 500 * 1000 + 13;

int n, k;
vector<pair<int, int>> g[N];
long long dp[N][2];

void calc(int v, int p = -1) {
	long long cur = 0;
	vector<long long> adds;
	
	for (auto it : g[v]) {
		int to = it.x;
		int w = it.y;
		if (to == p)
			continue;
		calc(to, v);
		
		cur += dp[to][0];
		adds.pb(dp[to][1] + w - dp[to][0]);
	}
	
	sort(all(adds), greater<long long>());
	forn(i, min(sz(adds), k)) if (adds[i] > 0)
		cur += adds[i];
	
	dp[v][0] = dp[v][1] = cur;
	if (k <= sz(adds) && adds[k - 1] > 0)
		dp[v][1] -= adds[k - 1];
}

long long solve() {
    scanf("%d%d", &n, &k);
    forn(i, n) g[i].clear();
	forn(i, n - 1) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		--x; --y;
		g[x].pb(mp(y, w));
		g[y].pb(mp(x, w));
	}
	
	calc(0);
	
	return dp[0][0];
}

int main() {
	int q;
	scanf("%d", &q);
	forn(i, q) printf("%lld\n", solve());
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;

int t, n;
int a[N];
int nxt[N];
int dp[N];
map<int, int> nxtX[N];


int main() {	
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i)
			scanf("%d", a + i);
		for(int i = 0; i < n + 2; ++i){
			nxt[i] = -1;
			nxtX[i].clear();
			dp[i] = 0;
		}

		for(int i = n - 1; i >= 0; --i){
			if(nxtX[i + 1].count(a[i])){
				int pos = nxtX[i + 1][a[i]];
				assert(pos < n && a[pos] == a[i]);
				nxt[i] = pos;
				swap(nxtX[i], nxtX[pos + 1]);
				if(pos < n - 1)
					nxtX[i][a[pos + 1]] = pos + 1;
			}
			nxtX[i][a[i]] = i;
		}	

		long long res = 0;
		for(int i = n - 1; i >= 0; --i){
			if(nxt[i] == -1) continue;	
			dp[i] = 1 + dp[nxt[i] + 1];
			res += dp[i];
		}

		printf("%lld\n", res);
	}
	return 0;
} 

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

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

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

template<class A>
pair<A, A> upd(const pair<A, A> &mx, const A &val) {
    return {max(mx.x, val), max(mx.y, min(mx.x, val))};
}

vector<int> cnt, sum;
vector<int> prv;

li getSum(int l, int r) {
    return sum[r] - sum[l];
}

li ans, rx, ry;
void updAns(li x, li y) {
    if (x < 2 || y < 2)
        return;
    if (ans >= x * y)
        return;
    ans = x * y;
    rx = x, ry = y;
}

inline void solve() {
    cnt.assign(*max_element(all(a)) + 1, 0);
    fore(i, 0, n)
        cnt[a[i]]++;
    sum.assign(sz(cnt) + 1, 0);
    fore(i, 0, sz(cnt))
        sum[i + 1] = sum[i] + cnt[i];
    prv.assign(sz(cnt), -1);
    fore(i, 0, sz(prv)) {
        if(i > 0)
            prv[i] = prv[i - 1];
        if(cnt[i] > 0)
            prv[i] = i;
    }

    ans = 0;
    fore(y, 2, sz(cnt)) {
        li cntY = 0;
        for(int i = 0; y * i < sz(cnt); i++)
            cntY += i * 1ll * getSum(i * y, min((i + 1) * y, sz(cnt)));

        pair<pt, pt> mx = {{-1, -1}, {-1, -1}};
        int lf = (sz(cnt) - 1) / y * y, rg = sz(cnt);
        while(lf >= 0) {
            int cntMore = (mx.x.x >= 0) + (mx.y.x >= 0);
            int val1 = prv[rg - 1];
            if (val1 >= lf) {
                mx = upd(mx, pt{val1 % y, val1});
                if (cnt[val1] == 1)
                    val1 = prv[val1 - 1];
                if (val1 >= lf)
                    mx = upd(mx, pt{val1 % y, val1});
            }

            if (mx.x.x >= 0) {
                li x = (lf + mx.x.x) / 2;
                li cur = cntY - lf / y;
                updAns(min(cur, x), y);
            }
            if (mx.y.x >= 0) {
                li x = lf + mx.y.x;
                li cur = cntY - 2 * (lf / y);
                updAns(min(cur, x), y);

                if(cntMore + (mx.x.y < rg) >= 2) {
                    x = lf + mx.x.x;
                    cur--;
                    updAns(min(cur, x), y);
                }
            }

            rg = lf;
            lf -= y;
        }
    }
    cout << ans << endl;
    cerr << rx << " " << ry << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cerr << fixed << setprecision(15);

    if(read()) {
        solve();

#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 101;
const int MAX_M = 1001;

int n, m, k;

vector<pair<int, int> > v[MAX_N];
int w[MAX_N];
int a[MAX_M], b[MAX_M], c[MAX_M], color[MAX_M];

set<pair<int, int> > s[MAX_N], s2;
int deg[MAX_N][MAX_M];
inline pair<int, int> get_s2(int i){
    return {s[i].begin()->first - s[i].rbegin()->first, i};
}
inline void change_edge_color(int edge, int d){
    int pos1 = a[edge];
    int pos2 = b[edge];
    assert(s[pos1].find({deg[pos1][color[edge]], color[edge]}) != s[pos1].end());
    s[pos1].erase({deg[pos1][color[edge]], color[edge]});
    s[pos2].erase({deg[pos2][color[edge]], color[edge]});
    deg[pos1][color[edge]] += d;
    deg[pos2][color[edge]] += d;
    s[pos1].insert({deg[pos1][color[edge]], color[edge]});
    s[pos2].insert({deg[pos2][color[edge]], color[edge]});
}
inline void change_color(int edge, int col){
    if (edge == 0 || edge > m || color[edge] == col)
        return;
    int pos1 = a[edge];
    int pos2 = b[edge];
    s2.erase(get_s2(pos1));
    s2.erase(get_s2(pos2));
    change_edge_color(edge, -1);
    color[edge] = col;
    change_edge_color(edge, 1);
    s2.insert(get_s2(pos1));
    s2.insert(get_s2(pos2));
}

vector<pair<int, int> > v2[MAX_N];
int deg2[MAX_N];
vector<int> vertices;
int used[MAX_N];
void dfs2(int pos){
    used[pos] = 2;
    for (auto e : v2[pos]){
        if (used[e.first] != 2){
            dfs2(e.first);
        }
    }
    vertices.push_back(pos);
}
int _col[2];
set<int> used3;
int i;
vector<int> euler;
void dfs3(int pos, int prev = -1, int pr2 = 0){
    while(!v2[pos].empty()){
        int ind = v2[pos].back().second;
        int to = v2[pos].back().first;
        v2[pos].pop_back();
        if (used3.find(ind) != used3.end()){
            continue;
        }
        used3.insert(ind);
        dfs3(to, ind, pos);
    }
    if (prev != -1){
        euler.push_back(prev);
    }
}

void stabilize_two_colors(const vector<int> &e, int col1, int col2){
    assert(!e.empty());
    v2[0].clear();
    for (auto edge : e){
        v2[a[edge]].clear();
        v2[b[edge]].clear();
        deg2[a[edge]] = 0;
        deg2[b[edge]] = 0;
        used[a[edge]] = 0;
        used[b[edge]] = 0;
    }
    for (auto edge : e){
        v2[a[edge]].push_back({b[edge], edge});
        v2[b[edge]].push_back({a[edge], edge});
    }
    vertices.clear();
    int u = m;
    for (auto edge : e){
        if (used[a[edge]] != 2){
            int k = (int) vertices.size();
            dfs2(a[edge]);
            bool find = false;
            for (int i = k; i < (int) vertices.size(); i++){
                int v = vertices[i];
                if (v2[v].size() % 2 == 1){
                    find = true;
                    ++u;
                    v2[v].push_back({0, u});
                    v2[0].push_back({v, u});
                }
            }
            if (!find){
                int v = vertices[k];
                for (int j = 0; j < 2; j++){
                    ++u;
                    v2[v].push_back({0, u});
                    v2[0].push_back({v, u});
                }
            }
        }
    }
    used3.clear();
    euler.clear();
    dfs3(0);
    for (int a : euler){
        change_color(a, col1);
        swap(col1, col2);
    }
}

void stabilize(const vector<int> &e){
    s2.clear();
    for (int i = 1; i <= n; i++){
        s[i].clear();
        for (int j = 1; j <= k; j++){
            deg[i][j] = 0;
        }
    }
    for (int edge : e){
        deg[a[edge]][color[edge]]++;
        deg[b[edge]][color[edge]]++;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= k; j++){
            s[i].insert({deg[i][j], j});
        }
        s2.insert(get_s2(i));
    }
    while(-s2.begin()->first > 2){

        int ind = s2.begin()->second;
        int col1 = s[ind].begin()->second;
        int col2 = s[ind].rbegin()->second;
        vector<int> e2;
        for (int edge : e){
            if (color[edge] == col1 || color[edge] == col2){
                e2.push_back(edge);
            }
        }
        stabilize_two_colors(e2, col1, col2);
    }
}

void make_random(vector<int> e){
    random_shuffle(e.begin(), e.end());
    for (int i = 0; i < (int) e.size(); i++){
        color[e[i]] = i % k + 1;
    }
    stabilize(e);
}

int change[MAX_N];

void build(vector<int> e){
    if ((int) e.size() <= n * k){
        make_random(e);
        return;
    }
    random_shuffle(e.begin(), e.end());
    vector<int> e1, e2;
    int s = (int) e.size() / 2;
    for (int i = 0; i < (int) e.size(); i++){
        if (i < s){
            e1.push_back(e[i]);
        }else{
            e2.push_back(e[i]);
        }
    }
    build(e1);
    build(e2);
    vector<pair<int, int> > v1(k), v2(k);
    for (int i = 1; i <= k; i++){
        v1[i - 1].first = v2[i - 1].first = 0;
        v1[i - 1].second = v2[i - 1].second = i;
    }
    for (int edge : e1){
        v1[color[edge] - 1].first++;
    }
    for (int edge : e2){
        v2[color[edge] - 1].first++;
    }
    sort(v1.rbegin(), v1.rend());
    sort(v2.begin(), v2.end());
    for (int i = 0; i < k; i++){
        change[v1[i].second] = i + 1;
    }
    for (int edge : e1){
        color[edge] = change[color[edge]];
    }
    for (int i = 0; i < k; i++){
        change[v2[i].second] = i + 1;
    }
    for (int edge : e2){
        color[edge] = change[color[edge]];
    }
    stabilize(e);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
#ifdef LOCAL
    freopen("/Users/antontsypko/tsypko/input.txt", "r", stdin);
#endif
    
    cin >> n >> m >> k;
    
    for (int i = 1; i <= n; i++){
        cin >> w[i];
    }
    
    ll sum = 0;
    vector<int> e;
    for (int i = 1; i <= m; i++){
        cin >> a[i] >> b[i];
        sum += w[a[i]] + w[b[i]];
        e.push_back(i);
    }
    
    build(e);
    
    for (int i = 1; i <= m; i++){
        assert(color[i]);
        cout << color[i] << endl;
    }
    
}

#include<bits/stdc++.h>

using namespace std;

int main() {
	int n; cin >> n;
	
	int curMax = 0;
	for(int i = 0; i < n; i++) {
		int curAns; cin >> curAns;
		curMax = max(curMax, curAns);
	}
	puts(curMax > 0 ? "HARD" : "EASY");
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n, d;
int m;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	cin >> n >> d;
	cin >> m;
	for(int i = 0; i < m; ++i){
		int x, y;
		cin >> x >> y;
		
		bool ok = true;
		if(!((x - y) <= d && (x - y) >= -d)) 
			ok = false;
		if(!((x + y) <= n + n - d && (x + y) >= d))
			ok = false;

		if(ok) puts("YES");
		else puts("NO");
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	cin >> n >> s;
	int sum = 0;
	for(int i = 0; i < n - 1; ++i){
		sum += s[i] - '0';
		
		bool ok = true;
		int pos = i + 1;
		int sum2 = 0;
		while(pos < n){
			sum2 = s[pos++] - '0';
			while(pos < n && sum2 + s[pos] - '0' <= sum){
				sum2 += s[pos] - '0';
				++pos;
			}
			if(sum2 != sum) ok = false;
		}
		
		if(sum2 != sum) ok = false;
		if(ok){
			puts("YES");
			return 0;
		}
	}
	
	puts("NO");	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b){
	return a? gcd(b % a, a) : b;
}

int main() {
	//freopen("input.txt", "r", stdin);
	
    long long n, m, k;
    cin >> n >> m >> k;
    
    bool isEven = k % 2 == 0;
    long long p = n * m;
	if(isEven) k /= 2;
	
	if(p % k != 0){
		cout << "NO" << endl;
		return 0;
	}
	
	long long x = gcd(n, k);
	k /= x;
	long long a = n / x;
		
	x = gcd(m, k);
	k /= x;
	assert(k == 1);
	long long b = m / x;
		
	
	if(!isEven){
		if(a < n)
			a += a;
		else{
			assert(b < m);
			b += b;
		}
	}
	
	cout << "YES" << endl;
	cout << "0 0\n";
	cout << 0 << ' ' << b << endl;
	cout << a << ' ' << 0 << endl;
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 9;

int n;
long long a[N];
int b[N];
int cnt[2][N];

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	cin >> n;
	for(int i = 0; i <n; ++i){
		cin >> a[i];
		b[i] = __builtin_popcountll(a[i]);	
	}
	
	long long res = 0;
	int sufSum = 0;
	cnt[0][n] = 1;
	for(int i = n - 1; i >= 0; --i){
		int sum = 0, mx = 0;
		int lstJ = i;
		int add = 0;
		for(int j = i; j < n && j - i < 65; ++j){
			sum += b[j];
			mx = max(mx, b[j]);
			if(mx > sum - mx && sum % 2 == 0) --add;
			lstJ = j;
		}		
		
		sufSum += b[i];
		add += cnt[sufSum & 1][i + 1];
		res += add;	
		
		cnt[0][i] = cnt[0][i + 1];
		cnt[1][i] = cnt[1][i + 1];
		if(sufSum & 1) ++cnt[1][i];
		else ++cnt[0][i];
	}
	
	cout << res << endl;
	return 0;
}

#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 MOD = int(1e9) + 7;

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

int norm(const li &a) {
	return norm(int(a % MOD));
}

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

const int N = 200 * 1000 + 555;

int n, q;
int a[N], w[N];

inline bool read() {
	if(!(cin >> n >> q))
		return false;
	fore(i, 0, n)
		assert(scanf("%d", &a[i]) == 1);
	fore(i, 0, n)
		assert(scanf("%d", &w[i]) == 1);
	return true;
}

li fW[N], fAW[N];

void inc(li f[N], int pos, li val) {
	for(; pos < N; pos |= pos + 1)
		f[pos] += val;
}

li sum(li f[N], int pos) {
	li ans = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		ans += f[pos];
	return ans;
}

li getSum(li f[N], int l, int r) {
	return sum(f, r - 1) - sum(f, l - 1);
}

int getNSum(li f[N], int l, int r) {
	return norm(sum(f, r - 1) - sum(f, l - 1));
}

inline void solve() {
	fore(i, 0, n) {
		a[i] -= i;
		inc(fW, i, w[i]);
		inc(fAW, i, mul(a[i], w[i]));
	}
	
	fore(_, 0, q) {
		int x, y;
		assert(scanf("%d%d", &x, &y) == 2);
		if(x < 0) {
			x = -x - 1;
			inc(fW, x, -w[x]);
			inc(fAW, x, -mul(a[x], w[x]));
			
			w[x] = y;
			inc(fW, x, w[x]);
			inc(fAW, x, mul(a[x], w[x]));
		} else {
			x--;
			li sum = getSum(fW, x, y);
			
			int lf = x, rg = y;
			while(rg - lf > 1) {
				int mid = (lf + rg) >> 1;
				if(2 * getSum(fW, x, mid) > sum)
					rg = mid;
				else
					lf = mid;
			}
			assert(x <= lf && lf < y);
			
			int ans = norm(mul(a[lf], getNSum(fW, x, lf)) - getNSum(fAW, x, lf));
			ans = norm(ans + norm(getNSum(fAW, lf, y) - mul(a[lf], getNSum(fW, lf, y))) );
			printf("%d\n", ans);
		}
	}
}

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

#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 x first
#define y second

typedef long long li;

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) {
	out << "[";
	fore(i, 1, int(v.size())) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

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

const int MOD = int(1e9) + 7;

int norm(int a) {
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}

int norm(const li &a) {
	return norm(int(a % MOD));
}

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

const int N = 300 * 1000 + 555;

int n, q;
int a[N], w[N];

inline bool read() {
	if(!(cin >> n >> q))
		return false;
	fore(i, 0, n)
		assert(scanf("%d", &a[i]) == 1);
	fore(i, 0, n)
		assert(scanf("%d", &w[i]) == 1);
	return true;
}

li TW[4 * N], TAW[4 * N];

void addVAl(li T[4 * N], int v, int l, int r, int pos, int val) {
	if(l + 1 == r) {
		assert(l == pos);
		T[v] += val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos < mid)
		addVAl(T, 2 * v + 1, l, mid, pos, val);
	else
		addVAl(T, 2 * v + 2, mid, r, pos, val);
	T[v] = T[2 * v + 1] + T[2 * v + 2];
}

li getSum(li T[4 * N], int v, int l, int r, int lf, int rg) {
	if(l == lf && r == rg)
		return T[v];
	int mid = (l + r) >> 1;
	li ans = 0;
	if(lf < mid)
		ans += getSum(T, 2 * v + 1, l, mid, lf, min(mid, rg));
	if(rg > mid)
		ans += getSum(T, 2 * v + 2, mid, r, max(lf, mid), rg);
	return ans;
}

int getNSum(li T[4 * N], int l, int r) {
	if(l >= r) return 0;
	return int(getSum(T, 0, 0, n, l, r) % MOD);
}

pair<int, li> getPos(int v, int l, int r, int lf, int rg, li val) {
	if(l == lf && r == rg) {
		if(TW[v] <= val)
			return make_pair(INF, TW[v]);
		if(l + 1 == r)
			return make_pair(l, 0);
	}
	int mid = (l + r) >> 1;
	
	int res = INF;
	li sum = 0;
	if(lf < mid) {
		auto cur = getPos(2 * v + 1, l, mid, lf, min(mid, rg), val);
		res = min(res, cur.x);
		sum += cur.y;
	}
	if(rg > mid && res == INF) {
		auto cur = getPos(2 * v + 2, mid, r, max(lf, mid), rg, val - sum);
		res = min(res, cur.x);
		sum += cur.y;
	}
	return make_pair(res, sum);
}

inline void solve() {
	fore(i, 0, n) {
		a[i] -= i;
		addVAl(TW, 0, 0, n, i, w[i]);
		addVAl(TAW, 0, 0, n, i, mul(a[i], w[i]));
	}
	
	fore(_, 0, q) {
		int x, y;
		assert(scanf("%d%d", &x, &y) == 2);
		if(x < 0) {
			x = -x - 1;
			addVAl(TW, 0, 0, n, x, -w[x]);
			addVAl(TAW, 0, 0, n, x, -mul(a[x], w[x]));
			
			w[x] = y;
			addVAl(TW, 0, 0, n, x, w[x]);
			addVAl(TAW, 0, 0, n, x, mul(a[x], w[x]));
		} else {
			x--;
			li sum = getSum(TW, 0, 0, n, x, y);
			int pos = getPos(0, 0, n, x, y, sum / 2).x;
			assert(x <= pos && pos < y);
			
			int ans = norm(mul(a[pos], getNSum(TW, x, pos)) - getNSum(TAW, x, pos));
			ans = norm(ans + norm(getNSum(TAW, pos, y) - mul(a[pos], getNSum(TW, pos, y))) );
			printf("%d\n", ans);
		}
	}
}

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

#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 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) {
	out << "[";
	fore(i, 0, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

const int MOD = int(1e9) + 7;

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

int binPow(int a, int k) {
	int ans = 1;
	while(k > 0) {
		if(k & 1) ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

const int M = 2000 * 1000 + 555;
const int N = 200 * 1000 + 555;

int n, p[N];

inline bool read() {
	if(!(cin >> n))
		return false;
	fore(i, 0, n)
		assert(scanf("%d", &p[i]) == 1);
	return true;
}

int minD[M];
vector<pt> ps[M];

void precalc() {
	iota(minD, minD + M, 0);
	fore(i, 2, M) {
		if(minD[i] < i)
			continue;
		
		for(li j = i * 1ll * i; j < M; j += i)
			minD[j] = min(minD[j], i);
	}
	
	fore(i, 2, M) {
		int v = i;
		ps[i].clear();
		
		while(v > 1) {
			int md = minD[v];
			if(ps[i].empty() || ps[i].back().x != md)
				ps[i].emplace_back(md, 0);
			ps[i].back().y++;
			v /= md;
		}
	}
}

int baseA[M], cntNotZero = 0;

int a[M];
int mark[M];

void insert(int v) {
	if(a[v] < 1) {
		a[v] = 1;
		mark[v] = 1;
		return;
	}
	for(auto p : ps[v - 1]) {
		a[p.x] = max(a[p.x], p.y);
		if(mark[p.x]) {
			mark[p.x] = 0;
			insert(p.x);
		}
	}
}

vector<int*> pnt;
vector<int> val;

void upd(int &pos, int nval) {
	pnt.push_back(&pos);
	val.push_back(pos);
	
	pos = nval;
}

void roll_back() {
	*(pnt.back()) = val.back();
	pnt.pop_back();
	val.pop_back();
}

bool ok[N];
int cntSame = 0;
vector<int> Top[4 * N];

void addOp(int v, int l, int r, int lf, int rg, int val) {
	if(l == lf && r == rg) {
		Top[v].push_back(val);
		return;
	}
	int mid = (l + r) >> 1;
	if(lf < mid)
		addOp(2 * v + 1, l, mid, lf, min(mid, rg), val);
	if(rg > mid)
		addOp(2 * v + 2, mid, r, max(lf, mid), rg, val);
}

void insertDC(int v) {
	if(a[v] < 1) {
		upd(a[v], 1);
		upd(mark[v], 1);
		if(a[v] == baseA[v])
			upd(cntSame, cntSame + 1);
		return;
	}
	for(auto p : ps[v - 1]) {
		if(a[p.x] < p.y) {
			upd(a[p.x], p.y);
			if(a[p.x] == baseA[p.x])
				upd(cntSame, cntSame + 1);
		}
		if(mark[p.x]) {
			upd(mark[p.x], 0);
			insertDC(p.x);
		}
	}
}

void calcAns(int v, int l, int r) {
	int curOp = sz(pnt);
	for(int cv : Top[v])
		insertDC(cv);
	
	if(l + 1 == r) {
		ok[l] = cntSame == cntNotZero;
	} else {
		int mid = (l + r) >> 1;
		calcAns(2 * v + 1, l, mid);
		calcAns(2 * v + 2, mid, r);
	}
	while(sz(pnt) > curOp)
		roll_back();
}

inline void solve() {
	memset(baseA, 0, sizeof baseA);
	memset(a, 0, sizeof a);
	memset(mark, 0, sizeof mark);
	
	fore(i, 0, n)
		insert(p[i]);
		
	cntNotZero = 0;
	fore(i, 0, M) {
		baseA[i] = a[i];
		cntNotZero += a[i] > 0;
	}
	
	memset(a, 0, sizeof a);
	memset(mark, 0, sizeof mark);
	fore(i, 0, n) {
		if(i > 0)
			addOp(0, 0, n, 0, i, p[i]);
		if(i + 1 < n)
			addOp(0, 0, n, i + 1, n, p[i]);
	}
	calcAns(0, 0, n);
	
	int lcm = 1;
	fore(i, 1, M)
		lcm = mul(lcm, binPow(i, baseA[i]));
	int add = 0;
	fore(i, 0, n)
		if(ok[i])
			add = 1;
	cout << (lcm + add) % MOD << endl;
}

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

#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 x first
#define y second

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

const int MOD = int(1e9) + 7;

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

int binPow(int a, int k) {
	int ans = 1;
	while(k > 0) {
		if(k & 1) ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

const int M = 2000 * 1000 + 555;

int minD[M];
vector<pt> ps[M];

inline void precalc() {
	iota(minD, minD + M, 0);
	
	fore(val, 2, M) {
		if(minD[val] < val)
			continue;
			
		for(li j = val * 1ll * val; j < M; j += val)
			minD[j] = min(minD[j], val);
	}
	
	fore(i, 2, M) {
		int v = i;
		ps[i].clear();
		
		while(v > 1) {
			int md = minD[v];
			if(ps[i].empty() || ps[i].back().x != md)
				ps[i].emplace_back(md, 0);
			ps[i].back().y++;
			v /= md;
		}
	}
}

int n;
vector<int> p;

inline bool read() {
	if(!(cin >> n))
		return false;
	p.assign(n, 0);
	fore(i, 0, n)
		assert(scanf("%d", &p[i]) == 1);
	return true;
}

int a[M], cnt[M];

inline void solve() {
	sort(p.begin(), p.end(), greater<int>());
	
	for(int& cp : p) {
		if(a[cp] == 0) {
			a[cp] = 1;
			cnt[cp] = 1;
		} else {
			cp--;
			for(auto np : ps[cp]) {
				if(a[np.x] < np.y) {
					a[np.x] = np.y;
					cnt[np.x] = 1;
				} else if(a[np.x] == np.y)
					cnt[np.x]++;
			}
		}
	}
	
	int add = 0;
	for(int cp : p) {
		bool un = false;
		for(auto np : ps[cp])
			un |= (a[np.x] == np.y && cnt[np.x] == 1);
		if(!un)
			add = 1;
	}
	
	int lcm = 1;
	fore(i, 2, M)
		lcm = mul(lcm, binPow(i, a[i]));
	cout << (lcm + add) % MOD << endl;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int t = clock();
#endif
	cout << fixed << setprecision(10);

	precalc();
	if(read()) {
		solve();	
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - t << endl;
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define PII pair <int, int>

const int N = 1e6 + 7;

int n;
int in[N];
int ans[N];
bool used[N];
vector <int> unused;

int cnt;
deque <PII> cur;
vector <PII> getEqual;

set <int> S;
vector <int> place[N];
vector <pair <int, int> > order;

bool check(){
	if(in[1] != 0 && in[n + n - 1] != 0 && in[1] != in[n + n - 1])
		return false;
	
	for(int i = 1; i + 1 < n + n; ++i)
		if(in[i] == in[i + 1] && in[i] != 0)
			return false;
	
	for(int i = 1; i < n + n; ++i){
		if(in[i] == 0)
			continue;

		if(place[in[i]].size() == 0)
			order.push_back({i, in[i]});
		place[in[i]].push_back(i);
	}
	
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j < place[i].size(); ++j)
			if(place[i][j]%2 != place[i][j - 1]%2)
				return false;
	
	S.insert(n + n);
	sort(order.begin(), order.end());
	
	for(auto v: order){
		auto it = S.lower_bound(v.first);
		if(*it < place[v.second].back())
			return false;
		
		for(int c: place[v.second])
			S.insert(c);
	}
	
	return true;
}

inline int get(){
    if(unused.size() == 0){
        puts("no");
        exit(0);
    }

	int ret = unused.back();
	unused.pop_back();
	return ret;
}

void go(){
	deque <PII> help;
	while(help.size() + cur.size() >= 3){
		if(help.size() < 3){
			help.push_back(cur.front());
			cur.pop_front();
			continue;
		}
		
		PII v1 = help.back(); help.pop_back();
		PII v2 = help.back(); help.pop_back();
		PII v3 = help.back(); help.pop_back();
		
		if(v1.st == 0 && v2.st != 0 && v3.st != 0){
			ans[v1.nd] = v3.st;
			help.push_back(v3);
		}
		else{
			help.push_back(v3);
			help.push_back(v2);
			help.push_back(v1);
		}
		
		if(cur.size() == 0)
			break;
		
		help.push_back(cur.front());
		cur.pop_front();
	}
	
	while(help.size()){
		cur.push_back(help.front());
		help.pop_front();
	}
}

void solve(int root){
	int need = (cur.size() + 1) / 2 - cnt;
	if(need < 0){
	    puts("no");
	    exit(0);
	}
	deque <PII> help;
	
	while(cur.size()){
		auto v = cur.front();
		cur.pop_front();

		if(need > 0 && v.st == 0){
			--need;
			v.st = get();
			ans[v.nd] = v.st;
		}
		
		help.push_back(v);
	}
	
	while(help.size()){
		cur.push_front(help.front());
		help.pop_front();
	}

	go();
	if(root == -1 && cur.back().st == 0){
		root = cur.front().st;
		ans[cur.back().nd] = root;

		cur.pop_front();
		cur.pop_back();
		solve(root);
		return;
	}
	
	reverse(cur.begin(), cur.end());
	go();
	
	while(cur.size() > 0){
		auto v = cur.front();
		cur.pop_front();
		
		if(v.st == 0)
			ans[v.nd] = root;
	}
	
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < n + n; ++i){
		scanf("%d", &in[i]);
		used[in[i]] = true;
	}
	
	if(!check()){
		puts("no");
		return 0;
	}
	
	if(in[1] != 0)
		in[n + n - 1] = in[1];
	else if(in[n + n - 1] != 0)
		in[1] = in[n + n - 1];
	
	for(int i = 1; i <= n; ++i){
		if(!used[i])
			unused.push_back(i);
		used[i] = false;
	}
	
	for(int i = 1; i < n + n; ++i)
		ans[i] = in[i];
	
	for(int i = 1; i < n + n; ++i){
		if(in[i] == 0){
			getEqual.push_back({in[i], i});
			continue;
		}

		if(used[in[i]]){
			cnt = 0;
			while(getEqual.back().st != in[i]){
				if(getEqual.back().st > 0){
					++cnt;
					used[getEqual.back().st] = false;
				}

				cur.push_front(getEqual.back());
				getEqual.pop_back();
			}
			
			solve(in[i]);
			continue;
		}
		
		getEqual.push_back({in[i], i});
		used[in[i]] = true;
	}
	
	cnt = 0;
	while(getEqual.size()){
		if(getEqual.back().st > 0){
			++cnt;
			used[getEqual.back().st] = false;
		}

		cur.push_front(getEqual.back());
		getEqual.pop_back();
	}
	
	solve(-1);
	puts("yes");
	for(int i = 1; i < n + n; ++i)
		printf("%d%c", ans[i], i == n + n - 1 ? '\n' : ' ');
	return 0;
}

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int mn = 1e9, mx = 0;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        mn = min(mn, x);
        mx = max(mx, x);
    }
    cout << max(0, (mx-mn)-n+1);    
}

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll gc = __gcd(c, d);
    c /= gc;
    d /= gc;
    cout << min(a/c, b/d);
}

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

const int N = 200100;

set<pair<int, int> > q;

int ans[N], n, a[N], m, k;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        q.insert({a[i], i});
    }
    int cnt = 0;
    while(!q.empty()){
        ++cnt;
        int pos = q.begin()->second;
        ans[pos] = cnt;
        q.erase(q.begin());
        while(true){
            auto it = q.lower_bound({a[pos]+1+k, 0});
            if (it == q.end())
                break;
            pos = it->second;
            q.erase(it);
            ans[pos] = cnt;
        }
    }
    cout << cnt << "\n";
    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

const int N = 200 * 1000 + 555;

int n, h;
pt a[N];

inline bool read() {
	if(!(cin >> n >> h))
		return false;
	fore(i, 0, n)
		assert(scanf("%d%d", &a[i].x, &a[i].y) == 2);
	sort(a, a + n);
	return true;
}

int ps[N];

int getH(int lf, int rg) {
	int l = int(lower_bound(a, a + n, pt(lf, -1)) - a);
	int r = int(lower_bound(a, a + n, pt(rg, -1)) - a);
	
	int sum = ps[r] - ps[l];
	if(l > 0)
		sum += max(0, a[l - 1].y - lf);
	
	assert(rg - lf - sum >= 0);
	return rg - lf - sum;
}

inline void solve() {
	ps[0] = 0;
	fore(i, 0, n)
		ps[i + 1] = ps[i] + (a[i].y - a[i].x);	
	
	int ans = 0;
	fore(i, 0, n) {
		int lx = a[i].y + 1;
		
		int lf = -(h + 1), rg = lx;
		while(rg - lf > 1) {
			int mid = (lf + rg) / 2;
			if(getH(mid, lx) > h)
				lf = mid;
			else
				rg = mid;
		}
		assert(getH(rg, lx) == h);
		ans = max(ans, lx - rg);
	}
	cout << ans << endl;
}

int main() {
	if(read()) {
		solve();
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int cnt[N];

int main()
{                
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		if(y != n)
		{
			puts("NO");
			return 0;
		}
		cnt[x]++;
	}
	int cur = 0;
	for(int i = 1; i < n; i++)
	{
		cur += cnt[i];
		if(cur > i)
		{
			puts("NO");
			return 0;
		}
	}
	int last = -1;
	puts("YES");
	set<int> unused;
	for(int i = 1; i < n; i++)
		unused.insert(i);
	for(int i = 1; i < n; i++)
	{
		if(cnt[i] > 0)
		{
			unused.erase(i);
			if(last != -1)
				printf("%d %d\n", last, i);
			last = i;
			cnt[i]--;
		}
		while(cnt[i] > 0)
		{
			printf("%d %d\n", last, *unused.begin());
			last = *unused.begin();
			cnt[i]--;
			unused.erase(unused.begin());
		}
	}
	printf("%d %d\n", last, 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()

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

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

const int N = 100 * 1000 + 555;

int n[2], y[2];
int x[2][N];

inline bool read() {
	fore(k, 0, 2) {
		if(!(cin >> n[k] >> y[k]))
			return false;
		fore(i, 0, n[k])
			assert(scanf("%d", &x[k][i]) == 1);
	}
	return true;
}

inline void solve() {
	int ans = 2;
	for(int dx = 1; dx < int(1e9); dx *= 2) {
		int mod = 2 * dx;
		map<int, int> cnt;
		
		int add[2] = {0, dx};
		fore(k, 0, 2) {
			fore(i, 0, n[k])
				cnt[(x[k][i] + add[k]) & (mod - 1)]++;
		}
		
		for(auto curAns : cnt)
			ans = max(ans, curAns.second);
	}
	cout << ans << endl;
}

int main() {
	if(read()) {
		solve();
	}
	return 0;
}