t = int(input())
for i in range(t):
    n = int(input())
    if n % 7 == 0:
        print(n)
    else:
        ans = -1
        for j in range(10):
            if (n - n % 10 + j) % 7 == 0:
                ans = n - n % 10 + j
        print(ans)

for _ in range(int(input())):
    s = input()
    print(min((len(s) - 1) // 2, s.count('0'), s.count('1')))

for _ in range(int(input())):
    hc, dc = map(int, input().split())
    hm, dm = map(int, input().split())
    k, w, a = map(int, input().split())
    for i in range(k + 1):
        nhc = hc + i * a
        ndc = dc + (k - i) * w
        if (hm + ndc - 1) // ndc <= (nhc + dm - 1) // dm:
            print("YES")
            break
    else:
        print("NO")

#include <bits/stdc++.h>

using namespace std;

const int N = 1001;

int main() {
  vector<int> d(N, N);
  d[1] = 0;
  for (int i = 1; i < N; ++i) {
    for (int x = 1; x <= i; ++x) {
      int j = i + i / x;
      if (j < N) d[j] = min(d[j], d[i] + 1);
    }
  }
  
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> b(n), c(n);
    for (int &x : b) cin >> x;
    for (int &x : c) cin >> x;
    int sum = 0;
    for (int x : b) sum += d[x];
    k = min(k, sum);
    vector<int> dp(k + 1, 0);
    for (int i = 0; i < n; ++i) {
      for (int j = k - d[b[i]]; j >= 0; j--) {
        dp[j + d[b[i]]] = max(dp[j + d[b[i]]], dp[j] + c[i]);
      }
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
  }
}

#include <bits/stdc++.h>

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

using namespace std;

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

vector<int> pr, rk;

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

bool unite(int a, int b){
	a = getp(a), b = getp(b);
	if (a == b) return false;
	if (rk[a] < rk[b]) swap(a, b);
	rk[a] += rk[b];
	pr[b] = a;
	return true;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	pr.resize(n);
	rk.resize(n);
	vector<edge> es(m);
	forn(i, m){
		scanf("%d%d%d", &es[i].v, &es[i].u, &es[i].w);
		--es[i].v, --es[i].u;
		es[i].w *= 2;
	}
	vector<int> ev(1, 0);
	forn(i, m) forn(j, i + 1) ev.push_back((es[i].w + es[j].w) / 2);
	sort(ev.begin(), ev.end());
	ev.resize(unique(ev.begin(), ev.end()) - ev.begin());
	vector<long long> base;
	vector<int> cnt;
	for (int x : ev){
		sort(es.begin(), es.end(), [&x](const edge &a, const edge &b){
			int wa = abs(a.w - x);
			int wb = abs(b.w - x);
			if (wa != wb) return wa < wb;
			return a.w > b.w;
		});
		forn(i, n) pr[i] = i, rk[i] = 1;
		long long cur_base = 0;
		int cur_cnt = 0;
		for (const auto &e : es) if (unite(e.v, e.u)){
			cur_base += abs(e.w - x);
			cur_cnt += x < e.w;
		}
		base.push_back(cur_base);
		cnt.push_back(cur_cnt);
	}
	int p, k, a, b, c;
	scanf("%d%d%d%d%d", &p, &k, &a, &b, &c);
	int x = 0;
	long long ans = 0;
	forn(q, k){
		if (q < p) scanf("%d", &x);
		else x = (x * 1ll * a + b) % c;
		int y = upper_bound(ev.begin(), ev.end(), 2 * x) - ev.begin() - 1;
		ans ^= (base[y] + (n - 1 - 2 * cnt[y]) * 1ll * (2 * x - ev[y])) / 2;
	}
	printf("%lld\n", ans);
	return 0;
}

#include <bits/stdc++.h>     

using namespace std;

typedef pair<long long, int> val;

#define x first 
#define y second

const int N = 200043;

val operator +(const val& a, const val& b)
{
    return make_pair(a.x + b.x, a.y + b.y);
}

val operator -(const val& a, const val& b)
{
    return make_pair(a.x - b.x, a.y - b.y);
}

val T[4 * N];
val Tfull[4 * N];
int f[4 * N];

val getVal(int v)
{
    if(f[v] == 1)
        return Tfull[v] - T[v];
    return T[v];
}

void push(int v)
{
    if(f[v] == 1)
    {
        f[v] = 0;
        T[v] = Tfull[v] - T[v];
        f[v * 2 + 1] ^= 1;
        f[v * 2 + 2] ^= 1;
    }   
}                

void upd(int v)
{
    Tfull[v] = Tfull[v * 2 + 1] + Tfull[v * 2 + 2];
    T[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2);
}

void setVal(int v, int l, int r, int pos, val cur)
{                                                           
    if(l == r - 1)
    {
        f[v] = 0;
        Tfull[v] = cur;
        T[v] = cur;
    }
    else
    {
        push(v);
        int m = (l + r) / 2;
        if(pos < m)
            setVal(v * 2 + 1, l, m, pos, cur);
        else
            setVal(v * 2 + 2, m, r, pos, cur);
        upd(v);
    }
}

void flipColor(int v, int l, int r, int L, int R)
{
    if(L >= R) return;
    if(l == L && r == R)
        f[v] ^= 1;
    else
    {
        push(v);
        int m = (l + r) / 2;
        flipColor(v * 2 + 1, l, m, L, min(m, R));
        flipColor(v * 2 + 2, m, r, max(L, m), R);
        upd(v);
    }
}

val getVal(int v, int l, int r, int L, int R)
{
    if(L >= R) return make_pair(0ll, 0);
    if(l == L && r == R) return getVal(v);
    int m = (l + r) / 2;
    val ans = make_pair(0ll, 0);
    push(v);
    ans = ans + getVal(v * 2 + 1, l, m, L, min(R, m));
    ans = ans + getVal(v * 2 + 2, m, r, max(L, m), R);
    upd(v);
    return ans;
}

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

int p[N], siz[N], d[N], nxt[N];
int tin[N], timer;
map<pair<int, int>, int> idx;
long long sum;
int cnt;
int active[N];
int active_cnt;

void dfs_sz(int v) 
{
    if (p[v] != -1) 
    {
        auto it = find(g[v].begin(), g[v].end(), p[v]);
        if (it != g[v].end())
            g[v].erase(it);
    }
    siz[v] = 1;
    for (int &u : g[v]) 
    {
        p[u] = v;
        d[u] = d[v] + 1;
        dfs_sz(u);
        siz[v] += siz[u];
        if (siz[u] > siz[g[v][0]])
            swap(u, g[v][0]);
    }
}

void dfs_hld(int v) 
{
    tin[v] = timer++;
    for (int u : g[v]) 
    {
        nxt[u] = (u == g[v][0] ? nxt[v] : u);
        dfs_hld(u);
    }
}

// [l; r] inclusive
void flipSegment(int l, int r) 
{
    flipColor(0, 0, n, l, r + 1);        
}

// [l; r] inclusive
val get(int l, int r) 
{
    return getVal(0, 0, n, l, r + 1);   
}

void flipPath(int v, int u) 
{
    for (; nxt[v] != nxt[u]; u = p[nxt[u]]) 
    {
        if (d[nxt[v]] > d[nxt[u]]) swap(v, u);
        flipSegment(tin[nxt[u]], tin[u]);
    }
    if (d[v] > d[u]) swap(v, u);
    flipSegment(tin[v], tin[u]);
}

val getPath(int v, int u) 
{
    val res = make_pair(0ll, 0);
    for (; nxt[v] != nxt[u]; u = p[nxt[u]]) 
    {
        if (d[nxt[v]] > d[nxt[u]]) swap(v, u);
        // update res with the result of get()
        res = res + get(tin[nxt[u]], tin[u]);
    }
    if (d[v] > d[u]) swap(v, u);
    res = res + get(tin[v], tin[u]);
    return res;
}

void activate_vertex(int x)
{
    int id = 0;
    if(p[x] != -1)
    {                       
        id = idx[make_pair(x, p[x])];
        val v = getPath(0, p[x]);
        flipPath(0, p[x]);
        sum -= v.x;
        cnt -= v.y;
        v = getPath(0, p[x]);
        sum += v.x;
        cnt += v.y;
    }                   
    cnt++;
    sum += id;
    setVal(0, 0, n, tin[x], make_pair((long long)(id), 1));
    active[x] = 1;
    active_cnt++;   
}          

void init_hld(int root = 0) 
{
    d[root] = 0;
    nxt[root] = root;
    p[root] = -1;
    timer = 0;
    dfs_sz(root);
    dfs_hld(root);
}

int currentSize[N];

int dfsSolution(int x, vector<int>& edges)
{
    if(!active[x]) return 0;
    currentSize[x] = 1;
    for(auto y : g[x])
        if(y != p[x])
            currentSize[x] += dfsSolution(y, edges);
    if(currentSize[x] % 2 == 1)
        edges.push_back(idx[make_pair(x, p[x])]);
    return currentSize[x];   
}

void outputSolution()
{
    vector<int> edges;
    if(cnt * 2 == active_cnt)
    {
        dfsSolution(0, edges);
        sort(edges.begin(), edges.end());
    }
    printf("%d", int(edges.size()));
    for(auto x : edges) printf(" %d", x);
    puts("");
    fflush(stdout);
}

void processQuery(int v)
{
    activate_vertex(v);
    if(cnt * 2 == active_cnt)
        printf("%lld\n", sum);
    else
        puts("0");
    fflush(stdout);
}

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);
        idx[make_pair(x, y)] = i;
        idx[make_pair(y, x)] = i;
    }   
    
    init_hld();         
    activate_vertex(0); 
    while(true)
    {
        int t;
        scanf("%d", &t);       
        if(t == 3)
            break;
        if(t == 2)
            outputSolution();
        if(t == 1)
        {
            int v;          
            scanf("%d", &v);
            --v;
            processQuery(v);
        } 
    }
}

#include <bits/stdc++.h>

using namespace std;



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        vector <int> b(7);

        for(int i = 0; i < 7; i++)
            cin >> b[i];

        cout << b[0] << ' ' << b[1] << ' ' << b[6] - b[0] - b[1] << endl;
    }
}

for _ in range(int(input())):
	n = int(input())
	s = input().split()
	for i in range(n - 3):
		if s[i][1] != s[i + 1][0]:
			s.insert(i + 1, s[i][1] + s[i + 1][0])
			break
	else:
		s.append(s[-1][1] + 'a')
	print(s[0][0], end="")
	for i in range(n - 1):
		print(s[i][1], end="")
	print()

#include <bits/stdc++.h>     

using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<long long> g(a.begin(), a.begin() + 2);
    for(int i = 0; i < n; i++)
    {
        g[i % 2] = __gcd(g[i % 2], a[i]);
    }  
    vector<bool> good(2, true);
    for(int i = 0; i < n; i++)
    {
        good[i % 2] = good[i % 2] && (a[i] % g[(i % 2) ^ 1] > 0);
    }   
    long long ans = 0;
    for(int i = 0; i < 2; i++)
        if(good[i])
            ans = max(ans, g[i ^ 1]);
    cout << ans << endl;
}

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

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    a = sorted(a)
    cost = sum(a[0:n-2*k]) + sum(map(lambda x: a[x+n-2*k] // a[x+n-k], range(0, k)))
    print(cost)
    
t = int(input())
for i in range(t):
    solve()

#include <bits/stdc++.h>

using namespace std;
using li = long long;

const int N = 50013;

int b[N];
int a[N];

void solve() {
    
    int n;
    cin >> n;

    li sumb = 0;
    for(int i = 0; i < n; i++) {
        cin >> b[i];
        sumb += b[i];
    }

    li d = n * 1ll * (n + 1) / 2;

    if(sumb % d != 0) {
        cout << "NO" << endl;
        return;
    }

    li suma = sumb / d;

    for(int i = n - 1; i >= 0; i--) {
        li res = (b[i] - b[(i + 1) % n] + suma);
        if(res % n != 0 || res <= 0) {
            cout << "NO" << endl;
            return;
        }

        a[(i + 1) % n] = res / n;
    }

    cout << "YES" << endl;
    for(int i = 0; i < n; i++)
        cout << a[i] << ' ';
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

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

a, b = map(int, input().split())
s = bin(b)[2:]
t = bin(a)[2:]
if s == t:
    print("YES")
    exit(0)
for q in [t + '1', t.strip('0')]:
    for l in range(len(s) - len(q) + 1):
        r = len(s) - len(q) - l
        if '1' * l + q + '1' * r == s or '1' * l + q[::-1] + '1' * r == s:
            print("YES")
            exit(0)
print("NO")

#include<bits/stdc++.h>

using namespace std;

string go(string t)
{
    while(t.back() == '0') t.pop_back();
    reverse(t.begin(), t.end());
    return t;
}

string to_bin(long long x)
{
    if(x == 0)
        return "";
    else
    {
        string s = to_bin(x / 2);
        s.push_back(char('0' + x % 2));
        return s;
    }
}

int main()
{
    long long x, y;
    cin >> x >> y;
    set<string> used;
    queue<string> q;
    q.push(to_bin(x));
    used.insert(to_bin(x));
    while(!q.empty())
    {
        string k = q.front();
        q.pop();
        if(k.size() > 100) continue;
        for(int i = 0; i < 2; i++)
        {
            string k2 = go(k + string(1, char('0' + i)));
            if(!used.count(k2))
            {
                used.insert(k2);
                q.push(k2);
            }
        }
    }
    if(used.count(to_bin(y)))
        cout << "YES\n";
    else
        cout << "NO\n";
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 400 * 1000 + 13;

int n, m, k;
int a[N], b[N];
int q[N];

int p[N];
multiset<int> wst[N], bst[N];
long long sum;

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

void unite(int a, int b){
	a = getp(a), b = getp(b);
	if (wst[a].size() + bst[a].size() < wst[b].size() + bst[b].size()) swap(a, b);
	for (auto it : wst[b])
		wst[a].insert(it);
	for (auto it : bst[b])
		bst[a].insert(it);
	wst[b].clear();
	bst[b].clear();
	while (!bst[a].empty() && !wst[a].empty() && *bst[a].begin() < *wst[a].rbegin()){
		sum -= *bst[a].begin();
		sum += *wst[a].rbegin();
		bst[a].insert(*wst[a].rbegin());
		wst[a].insert(*bst[a].begin());
		bst[a].erase(bst[a].begin());
		wst[a].erase(--wst[a].end());
	}
	p[b] = a;
}

long long ans[N];

struct event{
	int x, t, i;
};

int main() {
	scanf("%d%d%d", &n, &m, &k);
	forn(i, n)
		scanf("%d", &a[i]);
	forn(i, m)
		scanf("%d", &b[i]);
	forn(i, k)
		scanf("%d", &q[i]);
	vector<pair<int, int>> tot;
	forn(i, n) tot.push_back({a[i], 1});
	forn(i, m) tot.push_back({b[i], 0});
	sort(tot.begin(), tot.end());
	sum = accumulate(a, a + n, 0ll);
	forn(i, n + m){
		p[i] = i;
		wst[i].clear();
		bst[i].clear();
		if (tot[i].second) bst[i].insert(tot[i].first);
		else wst[i].insert(tot[i].first);
	}
	vector<event> ev;
	forn(i, n + m - 1) ev.push_back({tot[i + 1].first - tot[i].first, 0, i});
	forn(i, k) ev.push_back({q[i], 1, i});
	sort(ev.begin(), ev.end(), [](const event &a, const event &b){
		if (a.x != b.x) return a.x < b.x;
		return a.t < b.t;
	});
	for (auto it : ev){
		if (it.t == 0)
			unite(it.i, it.i + 1);
		else
			ans[it.i] = sum;
	}
	forn(i, k) printf("%lld\n", ans[i]);
}

#include<bits/stdc++.h>

using namespace std;

long long get(const vector<int>& pcnt, const vector<long long>& psum, pair<int, int> seg)
{
    int L = seg.first;
    int R = seg.second;
    int cnt = pcnt[R] - pcnt[L];
    return psum[R] - psum[R - cnt];
}

int main()
{
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    vector<int> a(n), b(m);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < m; i++)
    {
        scanf("%d", &b[i]);
    }
    vector<int> pcnt = {0};
    vector<long long> psum = {0ll};
    vector<pair<int, int>> order;
    for(int i = 0; i < n; i++) order.push_back(make_pair(a[i], 1));
    for(int i = 0; i < m; i++) order.push_back(make_pair(b[i], 0));
    sort(order.begin(), order.end());
    int z = n + m;
    for(int i = 0; i < z; i++)
    {
        pcnt.push_back(pcnt.back() + order[i].second);
        psum.push_back(psum.back() + order[i].first);
    }
    long long cur = 0;
    for(int i = 0; i < n; i++)
        cur += a[i];
    set<pair<int, int>> segs;
    for(int i = 0; i < z; i++)
        segs.insert(make_pair(i, i + 1));
    map<int, vector<int>> events;
    for(int i = 0; i < z - 1; i++)
        events[order[i + 1].first - order[i].first].push_back(i);
    vector<pair<int, long long>> ans = {{0, cur}};
    for(auto x : events)
    {
        int cost = x.first;
        vector<int> changes = x.second;
        for(auto i : changes)
        {
            auto itr = segs.upper_bound(make_pair(i, int(1e9)));
            auto itl = prev(itr);
            pair<int, int> pl = *itl;
            pair<int, int> pr = *itr;
            cur -= get(pcnt, psum, pl);
            cur -= get(pcnt, psum, pr);
            pair<int, int> p = make_pair(pl.first, pr.second);
            cur += get(pcnt, psum, p);
            segs.erase(pl);
            segs.erase(pr);
            segs.insert(p);
        }
        ans.push_back(make_pair(cost, cur));
    }              
    for(int i = 0; i < q; i++)
    {
        int k;
        scanf("%d", &k);
        int pos = upper_bound(ans.begin(), ans.end(), make_pair(k + 1, -1ll)) - ans.begin() - 1;
        printf("%lld\n", ans[pos].second);
    }
}

t = int(input())
for i in range(t):
    x, y = map(int, input().split())
    xc = -1
    yc = -1
    for j in range(0, 51):
        for k in range(0, 51):
            if 2 * (j + k) == x + y and 2 * (abs(x - j) + abs(y - k)) == x + y:
                xc, yc = j, k
    print(xc, yc)

t = int(input())
for i in range(t):
    n, a, b = map(int, input().split())
    p = [a]
    for j in range(n, 0, -1):
        if j != a and j != b:
            p.append(j)
    p.append(b)
    if(len(p) == n and min(p[0:n//2]) == a and max(p[n//2:n]) == b):
        print(*p)
    else:
        print(-1)

#include <bits/stdc++.h>

using namespace std;

long long get(int x) {
    return x * 1ll * (x + 1) / 2;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int t;
    cin >> t;
    while (t--) {
        int k;
        long long x;
        cin >> k >> x;
        long long l = 1, r = 2 * k - 1;
        long long res = 2 * k - 1;
        bool over = false;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (mid >= k) {
                over = (get(k) + get(k - 1) - get(2 * k - 1 - mid) >= x);
            } else {
                over = (get(mid) >= x);
            }
            if (over) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        cout << res << endl;
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

bool get(long long a, long long b, long long x) {
    if (a == x || b == x) return true;
    if (a < b) swap(a, b);
    if (b > a - b) b = a - b;
    if (x > max(a, b) || a == 0 || b == 0) return false;
    long long cnt = max(1ll, (a - max(x, b)) / (2 * b));
    return get(a - b * cnt, b, x);
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int t;
    cin >> t;
    while (t--) {
        long long a, b, x;
        cin >> a >> b >> x;
        if (get(a, b, x)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}

#include <bits/stdc++.h>     

using namespace std;

const int N = 200043;
const int K = 20;
vector<int> idx[N];
int m[N], k[N];

bool frac_greater(pair<int, int> a, pair<int, int> b)
{
    return a.first * b.second > a.second * b.first;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d %d", &m[i], &k[i]);
        idx[m[i]].push_back(i);
    }

    vector<int> cert;
    pair<int, int> ans = {0, 1};
    for(int i = 1; i <= K; i++)
    {
        vector<int> score(N);
        for(int j = 0; j < n; j++)
            score[m[j]] += min(i, k[j]);
        vector<pair<int, int>> aux;
        for(int j = 0; j < N; j++)
            aux.push_back(make_pair(score[j], j));
        sort(aux.rbegin(), aux.rend());
        pair<int, int> cur_ans = {0, i};
        vector<int> cur_cert;
        for(int j = 0; j < i; j++)
        {
            cur_ans.first += aux[j].first;
            cur_cert.push_back(aux[j].second);
        }
        if(frac_greater(cur_ans, ans))
        {
            ans = cur_ans;
            cert = cur_cert;
        }
    }
    cout << cert.size() << endl;
    shuffle(cert.begin(), cert.end(), mt19937(time(NULL)));
    for(auto x : cert) cout << x << " ";
    cout << endl;
}

#include<bits/stdc++.h>

using namespace std;

int n, m;

#define x first
#define y second

typedef pair<int, int> comb;

comb norm(const comb& a)
{
    return make_pair(min(a.x, n), min(a.y, m));
}

bool good(const comb& a)
{
    return a.x == n || a.y == m;
}

bool comp(const comb& a, const comb& b)
{
    if(a.x != b.x)
        return a.x > b.x;
    return a.y > b.y;
}

int main()
{
    scanf("%d %d", &n, &m);
    int v;
    scanf("%d", &v);
    set<comb> s;
    for(int i = 0; i < v; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        s.insert(make_pair(x, y));
    }
    int steps = 0;
    vector<comb> cur;
    cur.push_back(make_pair(1, 1));
    while(true)
    {
        if(cur[0] == make_pair(n, m))
            break;
        vector<comb> ncur;
        for(auto x : cur)
        {
            int sum = x.x + x.y;
            if(s.count(x))
                sum++;
            comb z = x;
            z.x = sum;
            ncur.push_back(norm(z));
            z = x;
            z.y = sum;
            ncur.push_back(norm(z));
        }
        sort(ncur.begin(), ncur.end(), comp);
        int mx = 0;
        vector<comb> ncur2;
        for(auto x : ncur)
        {
            if(x.y <= mx) continue;
            mx = max(mx, x.y);
            ncur2.push_back(x);
        }
        cur = ncur2;
        steps++;
    }
    printf("%d\n", steps);
}

#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) {
    fore(i, 0, sz(v)) {
        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 mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}

const int MX = int(1e6) + 55;
int n;
li total;
int cnt[MX];

inline bool read() {
    if(!(cin >> n))
        return false;
    total = 0;
    fore (i, 0, n) {
        int k; cin >> k;
        cnt[k]++;
        total += k;
    }
    return true;
}

int fact[MX];

inline void solve() {
    fact[0] = 1;
    fore (i, 1, MX)
        fact[i] = mul(fact[i - 1], i);
    
    int ansSum = 0;
    int ansCnt = 1;
    
    for (int lvl = MX - 1; lvl > 1; lvl--) {
        ansCnt = mul(ansCnt, mul(fact[cnt[lvl]], fact[cnt[lvl]]));
        
        //each color gives (lvl - 1) * (r_i - l_i)
        // or (lvl - 1) * (sum r_i - sum l_i)
        // l_i is permutation of [0,..., cnt[lvl]), so sum l_i = (cnt[lvl] - 1) * cnt[lvl] / 2
        // r_i is permutation of [total - cnt[lvl],..., total), so sum = cnt[lvl] * (total - cnt[lvl]) + (cnt[lvl] - 1) * cnt[lvl] / 2
        
        ansSum = norm(ansSum + mul(mul(lvl - 1, cnt[lvl]), (total - cnt[lvl]) % MOD));
        
        total -= 2 * cnt[lvl];
        cnt[lvl - 2] += cnt[lvl];
    }
    
    ansCnt = mul(ansCnt, fact[cnt[1]]);
    
    cout << ansSum << " " << ansCnt << 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);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

fun main() = repeat(readLine()!!.toInt()) {
  val s = readLine()!!
  val l = s.count({ it == '<' })
  val g = s.count({ it == '>' })
  if (l > 0 && g > 0) println("?")
  else if (l > 0) println("<");
  else if (g > 0) println(">");
  else println("=");
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val (d1, v1) = readLine()!!.split(' ').map { it.toInt() }
        val (d3, v3) = readLine()!!.split(' ').map { it.toInt() }
        val d2 = readLine()!!.toInt()

        fun isPossible(d1: Int, v1: Int, d2: Int, v2: Int) = (v2 - v1) <= (d2 - d1)

        for (v2 in v1..v3) {
            if (isPossible(d1, v1, d2, v1) && isPossible(d2, v2, d3, v3)) {
                println(v2)
                break
            }
        }
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        var l = 0
        var r = 4e5.toInt()
        for (i in 1..n) {
            val pairs = readLine()!!.split(' ')
            val limit = pairs[0].commonSuffixWith(pairs[1]).length
            if (pairs[2] == "0")
                l = maxOf(l, limit + 1)
            else
                r = minOf(r, limit)
        }
        println(maxOf(0, r - l + 1))
        if (r - l + 1 > 0)
           println((l..r).joinToString(" "))
    }
}

fun main() {
    val (n, m) = readLine()!!.split(' ').map { it.toInt() }
    val cntPairs = Array(n) { IntArray(n) { 0 } }
    val cntFirst = IntArray(n) { 0 }
    val cntLast = IntArray(n) { 0 }

    val firstPair = readLine()!!.split(' ').map { it.toInt() - 1 }
    for (i in 2..m) {
        val (f, l) = readLine()!!.split(' ').map { it.toInt() - 1 }
        cntPairs[f][l]++
        cntFirst[f]++
        cntLast[l]++
    }

    fun I(a: Boolean) = if (a) 1 else 0

    var worstPlace = 0
    for (w in 0 until n) {
        for (l in 0 until n) {
            if (w == l)
                continue
            val yourScore = I(w == firstPair[0]) + I(l == firstPair[1])
            var place = 1
            if (yourScore < 2)
                place += cntPairs[w][l]
            if (yourScore < 1)
                place += cntFirst[w] + cntLast[l] - 2 * cntPairs[w][l]
            worstPlace = maxOf(worstPlace, place)
        }
    }
    println(worstPlace)
}

@file:Suppress("CanBeVal")
 
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
 
private fun solve() {
    var n = readInt()
    var s = readLn()
    var a = readLn()
    var j = -1
    for (i in a.indices) {
        if (a[i] == '1') {
            if (j >= 0 && ((i - j) == 1 || (i - j) == 3)) {
                println(-1)
                return
            }
            j = i
        }
    }
    var i = 0
    var res = 0
    while (i < a.length) {
        if (a[i] == '1') {
            j = i
            while (j < a.length && a[j] == '1') {
                j += 2
            }
 
            if (j == i + 2) {
                res += minOf(diff(s.substring(i, i + 4), "(())"),
                        diff(s.substring(i, i + 4), "()()"))
            } else {
                for (k in i .. j step 2) {
                    res += diff(s.substring(k, k + 2), "()")
                }
            }
            i = j + 1
        } else {
            i++
        }
    }
    println(res)
}
 
private fun diff(a: String, b: String): Int {
    var res = 0
    for (i in a.indices) {
        if (a[i] != b[i]) res++
    }
    return res
}
 
// TEMPLATE
fun main(args: Array<String>) {
    reader = BufferedReader(InputStreamReader(System.`in`))
    out = PrintWriter(OutputStreamWriter(System.out))
    repeat(readInt()) {
        solve()
    }
    out.close()
}
 
private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
        tokenizer = StringTokenizer(readLn())
    }
    return tokenizer!!.nextToken()
}
 
private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
    a.forEach { print("$it ") }
    println()
}
 
private fun println(a: IntArray) {
    a.forEach { print("$it ") }
    println()
}
 
private fun println(a: LongArray) {
    a.forEach { print("$it ") }
    println()
}
 
private fun <T> println(a: Collection<T>) {
    a.forEach { print("$it ") }
    println()
}
 
private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    return Comparator { a, b ->
        val res = a.first.compareTo(b.first)
        if (res == 0) a.second.compareTo(b.second) else res
    }
}

@file:Suppress("CanBeVal")
 
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
 
private fun solve() {
    var (n, m) = readInts()
    var k = intarr(n)
    var t = intarr(n)
    for (i in k.indices) {
        var (kk, tt) = readInts()
        k[i] = kk
        t[i] = tt
    }
    var s1 = 0
    var s2 = 0
    var d = intarr(m + 1, -1)
    d[0] = 0
    for (i in k.indices) {
        if (t[i] == 2) {
            s1 += k[i]
            for (j in m downTo 0) {
                if (d[j] != -1 && j + k[i] <= m && d[j + k[i]] == -1) {
                    d[j + k[i]] = i
                }
            }
        } else {
            s2 += k[i]
        }
    }
    for (i in 0..m) {
        if (d[i] == -1) continue
        if (maxOf(i * 2 - 1, (s1 - i) * 2) + s2 > m) continue
        var c = BooleanArray(n)
        var x = i
        while (x > 0) {
            c[d[x]] = true
            x -= k[d[x]]
        }
        var res = intarr(n)
        var kk = 1
        for (i in 0 until n) {
            if (t[i] == 2 && c[i]) {
                res[i] = kk
                kk += k[i] * 2
            }
        }
        kk = 2
        for (i in 0 until n) {
            if (t[i] == 2 && !c[i]) {
                res[i] = kk
                kk += k[i] * 2
            }
        }
        kk = m + 1
        for (i in 0 until n) {
            if (t[i] == 1) {
                kk -= k[i]
                res[i] = kk
            }
        }
        println(res)
        return
    }
    println(-1)
}
 
// TEMPLATE
fun main(args: Array<String>) {
    reader = BufferedReader(InputStreamReader(System.`in`))
    out = PrintWriter(OutputStreamWriter(System.out))
//    repeat(readInt()) {
    solve()
//    }
    out.close()
}
 
private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
        tokenizer = StringTokenizer(readLn())
    }
    return tokenizer!!.nextToken()
}
 
private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
    a.forEach { print("$it ") }
    println()
}
 
private fun println(a: IntArray) {
    a.forEach { print("$it ") }
    println()
}
 
private fun println(a: LongArray) {
    a.forEach { print("$it ") }
    println()
}
 
private fun <T> println(a: Collection<T>) {
    a.forEach { print("$it ") }
    println()
}
 
private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    return Comparator { a, b ->
        val res = a.first.compareTo(b.first)
        if (res == 0) a.second.compareTo(b.second) else res
    }
}

class Attack(val a: Int, val b: Int, val i: Int)

fun main() {
	val (n, m) = readLine()!!.split(" ").map { it.toInt() }
	val ev = ArrayList<Attack>()

	for (i in 0 until n) {
		val k = readLine()!!.toInt()
		val a = readLine()!!.split(" ").map { it.toInt() }
		val b = readLine()!!.split(" ").map { it.toInt() }
		for (j in 0 until k) {
			ev.add(Attack(a[j], b[j], i))
		}
	}
	ev.sortWith(compareBy({ -it.b }, { it.i }))
	
	val INF = 1e18.toLong()
	val mx = m + n + 1
	val f = LongArray(mx) { -INF }
	
	fun update(pos: Int, x: Long) {
		var i = pos
		while (i < mx) {
			f[i] = maxOf(f[i], x)
			i = i or (i + 1)
		}
	}
	
	fun query(pos: Int) : Long {
		var res = -INF
		var i = pos
		while (i >= 0) {
			res = maxOf(res, f[i])
			i = (i and (i + 1)) - 1
		}
		return res
	}
	
	update(m - 1, 0L)
	for (it in ev) {
		val dp = query(it.i + it.b - 1) + it.a
		update(it.i + it.b, dp)
	}
	println(query(mx - 1))
}

@file:Suppress("CanBeVal")
 
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
 
private fun solveTest() {
    var n = readInt()
    var l = readInts()
    var r = readInts()
    var rr = r.toMutableList()
    rr.sort()
    var x = Integer.MAX_VALUE
    for (i in 0 until n) {
        x = minOf(x, rr[i] - i)
    }
    var a = (0 until n).toMutableList()
    a.sortBy { i -> l[i] }
    var j = 0
    var pq = PriorityQueue<Int>(compareBy { i -> r[i] })
    var res = intarr(n)
    for (t in x until x + n) {
        while (j < n && l[a[j]] <= t) {
            pq.add(a[j])
            j++
        }
        if (pq.isEmpty()) {
            println(-1)
            return
        }
        var q = pq.remove()
        if (r[q] < t) {
            println(-1)
            return
        }
        res[t - x] = q + 1
    }
    println(x)
    println(res)
}
 
private fun solve() {
    var t = readInt()
    while (t-- > 0) {
        solveTest()
    }
}
 
// TEMPLATE
fun main(args: Array<String>) {
    reader = BufferedReader(InputStreamReader(System.`in`))
    out = PrintWriter(OutputStreamWriter(System.out))
    solve()
    out.close()
}
 
private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
        tokenizer = StringTokenizer(readLn())
    }
    return tokenizer!!.nextToken()
}
 
private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
    a.forEach { print("$it ") }
    println()
}
 
private fun println(a: IntArray) {
    a.forEach { print("$it ") }
    println()
}
 
private fun <T> println(a: Collection<T>) {
    a.forEach { print("$it ") }
    println()
}
 
private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    return Comparator { a, b ->
        val res = a.first.compareTo(b.first)
        if (res == 0) a.second.compareTo(b.second) else res
    }
}

import java.util.*

fun main() = repeat(readLine()!!.toInt()) {
	val n = readLine()!!.toInt()
	val L = readLine()!!.split(" ").map { it.toInt() }
	val R = readLine()!!.split(" ").map { it.toInt() }
	
	val ord = Array(n, { i -> i })
	ord.sortWith({x : Int, y: Int -> L[x] - L[y]})
	
	val ans = IntArray(n)
	
	fun check(m: Int, fl: Boolean): Int {
		val cur = PriorityQueue<Int>(compareBy { R[it] })
		var j = 0
		var res = 0
		for (t in m until m + n) {
			while (j < n && L[ord[j]] <= t) {
				cur.add(ord[j])
				++j;
			}
			if (cur.isEmpty()) {
				res = 1
				break
			}
			if (R[cur.peek()] < t) {
				res = -1
				break
			}
			if (fl) ans[t - m] = cur.peek() + 1
			cur.poll()
		}
		return res;
	}
	
	var l = 1
	var r = 1e9.toInt()
	var res = -1
	while (l <= r) {
		val m = (l + r) / 2
		val tmp = check(m, false)
		if (tmp == 0) {
			res = m
			break
		}
		if (tmp == -1) {
			r = m - 1
		}
		else {
			l = m + 1
		}
	}
	
	println(res)
	if (res != -1) {
		check(res, true)
		println(ans.joinToString(" "))
	}
}

@file:Suppress("CanBeVal")
 
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
 
private class SegmentTree(private val size: Int) {
 
    class Item(val a: Long) {
        fun add(item: Item): Item {
            return if (a < item.a) this else item
        }
    }
 
    val NEUTRAL = Item(Long.MAX_VALUE)
 
    private val a: Array<Item>
 
    operator fun set(i: Int, v: Item) {
        set(0, 0, size, i, v)
    }
 
    private operator fun set(n: Int, l: Int, r: Int, i: Int, v: Item) {
        if (r == l + 1) {
            a[n] = a[n].add(v)
        } else {
            val m = (l + r) / 2
            if (i < m) {
                set(n * 2 + 1, l, m, i, v)
            } else {
                set(n * 2 + 2, m, r, i, v)
            }
            a[n] = a[n * 2 + 1].add(a[n * 2 + 2])
        }
    }
 
    fun sum(l: Int, r: Int): Item {
        return sum(0, 0, size, l, r)
    }
 
    private fun sum(n: Int, ll: Int, rr: Int, l: Int, r: Int): Item {
        return if (ll >= l && rr <= r) {
            a[n]
        } else if (ll >= r || l >= rr) {
            NEUTRAL
        } else {
            val m = (ll + rr) / 2
            sum(n * 2 + 1, ll, m, l, r).add(sum(n * 2 + 2, m, rr, l, r))
        }
    }
 
    init {
        a = Array<Item>(4 * size) { NEUTRAL }
    }
}
 
private fun solveTest() {
    var n = readInt()
    var a = readLongs(n - 1)
    var b = readLongs(n - 1)
    var c = readLongs(n)
 
    var d = longarr(n - 1)
    for (i in d.indices) {
        d[i] = when (i) {
            0 -> minOf(b[i], c[i])
            n - 2 -> minOf(b[i], c[i + 1])
            else -> b[i]
        }
    }
    for (i in 1..n - 2) {
        d[i] = minOf(d[i], c[i] + d[i - 1])
    }
    for (i in n - 3 downTo 0) {
        d[i] = minOf(d[i], c[i + 1] + d[i + 1])
    }
    var st = SegmentTree(n - 1)
    for (i in 0..n - 2) {
        st[i] = SegmentTree.Item(d[i] + a[i])
    }
    var ul = longarr(n - 1)
    var s = 0L
    for (i in 0..n - 2) {
        s += c[i]
        ul[i] = s
    }
    var ur = longarr(n - 1)
    s = 0L
    for (i in n - 2 downTo 0) {
        s += c[i + 1]
        ur[i] = s
    }
    var stl = SegmentTree(n - 1)
    for (i in 0..n - 2) {
        stl[i] = SegmentTree.Item(a[i] + ul[i])
    }
    var str = SegmentTree(n - 1)
    for (i in 0..n - 2) {
        str[i] = SegmentTree.Item(a[i] + ur[i])
    }
 
    var q = readInt()
    while (q-- > 0) {
        var (l, r) = readInts(2)
        l--; r--
        var res = st.sum(l, r).a
        if (l > 0) {
            var s1 = stl.sum(l, r).a - ul[l - 1]
//            var s2 = str.sum(0, l).a - ur[l - 1]
            res = minOf(res, s1)
        }
        if (r < n - 1) {
            var s1 = str.sum(l, r).a - ur[r]
//            var s2 = stl.sum(r, n - 1).a - ul[r]
            res = minOf(res, s1)
        }
        println(res)
    }
 
 
}
 
private fun solve() {
//    repeat(readInt()) {
        solveTest()
//    }
}
 
// TEMPLATE
fun main(args: Array<String>) {
    reader = BufferedReader(InputStreamReader(System.`in`))
    out = PrintWriter(OutputStreamWriter(System.out))
    solve()
    out.close()
}
 
private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
        tokenizer = StringTokenizer(readLn())
    }
    return tokenizer!!.nextToken()
}
 
private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
    a.forEach { print("$it ") }
    println()
}
 
private fun println(a: IntArray) {
    a.forEach { print("$it ") }
    println()
}
 
private fun <T> println(a: Collection<T>) {
    a.forEach { print("$it ") }
    println()
}
 
private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    return Comparator { a, b ->
        val res = a.first.compareTo(b.first)
        if (res == 0) a.second.compareTo(b.second) else res
    }
}

fun main() = repeat(readLine()!!.toInt()) {
  val (n, k) = readLine()!!.split(" ").map { it.toInt() }
  var ans = 0
  repeat(n) {
    val (l, r) = readLine()!!.split(" ").map { it.toInt() }
    if (l <= k) ans = maxOf(ans, r - k + 1)
  }
  println(ans)
}

fun main() {
    val t = readLine()!!.toInt()
    repeat(t) {
        val n = readLine()!!.toInt()
        val x = readLine()!!.split(" ").map { it.toInt() }
        var ans = false
        for (i in 1 until n) {
            if ((x[i] - x[i - 1]) % 2 == 0) {
                ans = true
            }
        }
        println(if (ans) "YES" else "NO")
    }
}

fun main() = repeat(readLine()!!.toInt()) {
  val (n, k) = readLine()!!.split(" ").map { it.toInt() }
  val s = readLine()!!
  val used = BooleanArray(n) { false }
  var cnt = s.count({ it == '1'})
  var pos = 0
  while (cnt > 0) {
    used[pos] = true
    if (s[pos] == '1') --cnt
    if (cnt == 0) break
    var lft = k
    while (lft > 0) {
      pos = (pos + 1) % n
      if (!used[pos]) --lft;
    }
  }
  println(used.count({ it }))
}

fun main() {
  val (n, m) = readLine()!!.split(" ").map { it.toInt() }
  val used = Array(n) { readLine()!! }.toSet()
  repeat(readLine()!!.toInt()) {
    val t = readLine()!!
    val s = (0..m).map { i -> t.removeRange(i..i) }.toSet()
    println(s.count { used.contains(it) } )
  }
}

fun main() {
	val n = readLine()!!.toInt()
	val a = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
	val b = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
	val m = readLine()!!.toInt()
	val c = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
	a.sort()
	b.sort()
	val pr = IntArray(n + 1) { -2e9.toInt() }
	for (i in 0 until n) {
		pr[i + 1] = maxOf(pr[i], b[i] - a[i])
	}
	val su = IntArray(n + 1) { -2e9.toInt() }
	for (i in (n-1) downTo 0) {
		su[i] = maxOf(su[i + 1], b[i + 1] - a[i])
	}
	val ans = IntArray(m)
	for (i in 0 until m) {
		var pos = a.binarySearch(c[i])
		if (pos < 0) {
			pos = -pos - 1
		}
		ans[i] = maxOf(pr[pos], su[pos], b[pos] - c[i])
	}
	println(ans.joinToString(" "))
}

fun main() {
  val s = readLine()!!.map { (it - '0').toInt() }.toIntArray()
  val pos = Array(2) { c -> s.indices.filter { s[it] == c }.toIntArray() }
  val sum = Array(2) { c -> s.runningFold(0) { cur, x -> cur + if (x == c) 1 else 0 }.toIntArray() }
  println((1..s.size).map { k -> 
    generateSequence(0) { i ->
      IntArray(2) { c -> pos[c].getOrElse(sum[c][i] + k) { s.size } }.maxOrNull()!!
    }.indexOf(s.size)
  }.joinToString(" "))
}

fun main() = repeat(readLine()!!.toInt()) {
  val (n, m) = readLine()!!.split(" ").map { it.toInt() }
  val a = Array(n) { readLine()!!.split(" ").map { it.toInt() } }
  val used = BooleanArray(111) { false }
  val ord = ArrayList<Int>()
  
  val dx = intArrayOf(0, 1, 0, -1)
  val dy = intArrayOf(1, 0, -1, 0)
  
  fun dfs(x : Int, y : Int) {
    ord.add(a[x][y])
    used[a[x][y]] = true
    for (i in 0 until 4) {
      val nx = x + dx[i]
      val ny = y + dy[i]
      if (0 <= nx && nx < n && 0 <= ny && ny < m && a[nx][ny] != 0 && !used[a[nx][ny]]) {
        dfs(nx, ny)
        ord.add(a[x][y])
      }
    }
  }
  
  var k = 0
  
  for (x in 0 until n) {
    for (y in 0 until m) {
      if (a[x][y] != 0) {
        k += 1
        if (ord.isEmpty()) dfs(x, y)
      }
    } 
  }
  
  if (ord.count() != 2 * k - 1) {
    return@repeat println(-1)
  }
  
  println("$k $k")
  for (x in 0 until k) {
    for (y in 0 until k) {
      print("${ord[x + y]} ")
    }
    println()
  }
}

fun main() {
  val AL = 5
  val (n, m) = readLine()!!.split(" ").map { it.toInt() }
  val s = Array(n) { readLine()!! }
  val res = LongArray(1 shl AL) { mask ->
    val d = IntArray(m) { 0 }
    var sum = 0L
    for (i in 0 until n) {
      for (j in 0 until m) {
        val cur = (mask shr (s[i][j] - 'A')) and 1 
        d[j] = if (cur == 1) d[j] + 1 else 0
      }
      val l = IntArray(m) { -1 }
      val q = IntArray(m) { 0 }
      var ptr = -1
      for (j in 0 until m) {
        while (ptr >= 0 && d[q[ptr]] >= d[j]) ptr -= 1
        if (ptr >= 0) l[j] = q[ptr]
        ptr += 1
        q[ptr] = j
      }
      val r = IntArray(m) { m }
      ptr = -1
      for (j in m - 1 downTo 0) {
        while (ptr >= 0 && d[q[ptr]] > d[j]) ptr -= 1
        if (ptr >= 0) r[j] = q[ptr]
        ptr += 1
        q[ptr] = j
      }
      for (j in 0 until m) sum += (j - l[j]) * (r[j] - j) * d[j].toLong()
    }
    sum
  }
  
  for (i in 0 until AL) {
    for (mask in 1 until (1 shl AL)) {
      if (((mask shr i) and 1) == 0) res[mask or (1 shl i)] -= res[mask]
    }
  }
  
  val ans = LongArray(AL + 1) { 0 }
  for (mask in 1 until (1 shl AL)) ans[mask.countOneBits()] += res[mask]
  
  println(ans.drop(1).joinToString(" "))
}

import java.util.Queue
import java.util.LinkedList

fun main() {
  val (n1, n2, m) = readLine()!!.split(" ").map { it.toInt() }
  val S = n1 + n2
  val T = S + 1
  val V = T + 1
  
  data class Edge(val y : Int, val c : Int, var f : Int, val cost : Int)
  
  val e = ArrayList<Edge>()
  val g = Array(V) { ArrayList<Int>() }
  
  fun addEdge(x : Int, y : Int, c : Int, cost : Int) {
    g[x].add(e.size)
    e.add(Edge(y, c, 0, cost))
    g[y].add(e.size)
    e.add(Edge(x, 0, 0, -cost))
  }
  
  var sum = 0
  readLine()!!.split(" ").mapIndexed { i, value ->
    val k = value.toInt()
    addEdge(i, T, 1, -k)
    sum += k
  }
  
  val deg = IntArray(n2) { 0 }
  repeat(m) {
    val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
    addEdge(y + n1, x, 1, 0)
    deg[y] += 1
  }
  
  for (i in 0 until n2) {
    addEdge(S, i + n1, deg[i] - 1, 0)
  }
  
  var mincost = 0
  
  fun enlarge() : Boolean {
    val q: Queue<Int> = LinkedList<Int>()
    val inq = IntArray(V) { 0 }
    val d = IntArray(V) { 1e9.toInt() }
    val p = IntArray(V) { -1 }
    val pe = IntArray(V) { -1 }
    
    q.add(S)
    inq[S] = 1
    d[S] = 0

    while (!q.isEmpty()) {
      val k = q.poll()
      g[k].forEach { a ->
        val (to, c, f, w) = e[a]
        if (c - f != 0 && d[to] > d[k] + w) {
          d[to] = d[k] + w
          p[to] = k
          pe[to] = a
          if (inq[to] == 0) {
            q.add(to)
            inq[to] = 1
          }
        }
      }
    }
    
    if (p[T] == -1) return false
    
    var cur = T
    while (cur != S) {
      mincost += e[pe[cur]].cost
      e[pe[cur]].f += 1
      e[pe[cur] xor 1].f -= 1
      cur = p[cur]
    }
    
    return true
  }
  
  while (enlarge());
  
  println(sum + mincost)
  
}

fun main() {
  val N = 500043
  val n = readLine()!!.toInt()
  val pts = Array(N) { ArrayList<Int>() }
  repeat(n) {
    val (x, y) = readLine()!!.split(" ").map { it.toInt() }
    pts[y].add(x)
  }
  pts.forEach { it.sort() }
  
  data class Event(val y : Int, val t : Int, val value : Int)
  
  fun recalc(v1 : ArrayList<Pair<Int, Int>>, v2 : ArrayList<Int>, flag : Boolean) : ArrayList<Pair<Int, Int>> {
    val events = ArrayList<Event>()
    if (flag) {
      v1.forEach { events.add(Event(it.first, 0, it.second)) }
      v2.forEachIndexed { i, value -> events.add(Event(value, 1, i + 1)) }
      events.add(Event(0, 1, 0))
      events.sortWith(compareBy({ -it.y }, { it.t }, { it.value }))
    } else {
      v1.forEach { events.add(Event(it.first, 0, it.second)) }
      v2.forEachIndexed { i, value -> events.add(Event(value, 1, v2.size - i)) }
      events.add(Event(N + 43, 1, 0))
      events.sortWith(compareBy({ it.y }, { it.t }, { it.value }))
    }
    var cur = 0
    val res = ArrayList<Pair<Int, Int>>()
    events.forEach { 
      if (it.t == 0) {
        cur = maxOf(cur, it.value)
      } else {
        res.add(Pair(it.y, it.value + cur))
      }
    }
    return res
  }
  
  fun calc(flag : Int) : Int {
    var cur = ArrayList<Pair<Int, Int>>()
    pts.forEachIndexed { i, value -> cur = recalc(cur, value, flag != i % 2) }
    var res = 0
    cur.forEach { res = maxOf(res, it.second) }
    return res
  }
  
  println(calc(0) + calc(1) - n)
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    vector<int> s(4);
    for (int& x : s) cin >> x;
    if (min(s[0], s[1]) > max(s[2], s[3]) || max(s[0], s[1]) < min(s[2], s[3]))
      cout << "NO\n";
    else
      cout << "YES\n";
  }
}

#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;
    sort(a.begin(), a.end(), [](int x, int y) {
      return x % 2 < y % 2;
    });
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        ans += __gcd(a[i], a[j] * 2) > 1;
      }
    }
    cout << ans << endl;
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    vector<vector<int>> lst(2, vector<int>(2, -1));
    long long ans = 0;
    for (int i = 0; i < int(s.size()); ++i) {
      int j = i - 1;
      int p = i & 1;
      if (s[i] != '1') j = min(j, max(lst[0][p ^ 1], lst[1][p]));
      if (s[i] != '0') j = min(j, max(lst[0][p], lst[1][p ^ 1]));
      ans += i - j;
      if (s[i] != '?') lst[s[i] - '0'][p] = i;
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  
  int k;
  cin >> k;
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  
  int n = 1 << k;
  vector<int> cnt(2 * n, 1);
  
  auto upd = [&](int i) {
    return cnt[i] = (s[i] != '0' ? cnt[i * 2 + 1] : 0) + (s[i] != '1' ? cnt[i * 2 + 2] : 0);
  };
  
  for (int i = n - 2; i >= 0; i--) {
    upd(i);
  }
  
  int q;
  cin >> q;
  while (q--) {
    int p;
    char c;
    cin >> p >> c;
    p = n - p - 1;
    s[p] = c;
    while (p) {
      upd(p);
      p = (p - 1) / 2;
    }
    cout << upd(0) << '\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 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 INF = int(1e9);
const li INF64 = li(1e18);

const int LOG = 20;

int q;
vector<int> a, c;
vector<int> p[LOG];

int main() {
	cin >> q;
	a.resize(q + 1);
	c.resize(q + 1);
	
	fore (lg, 0, LOG)
		p[lg].resize(q + 1);

	fore (lg, 0, LOG)
		p[lg][0] = 0;
	cin >> a[0] >> c[0];
	
	fore (id, 1, q + 1) {
		int tp; cin >> tp;
		if (tp == 1) {
			int pr; cin >> pr;
			cin >> a[id] >> c[id];
			
			p[0][id] = pr;
			fore (lg, 1, LOG)
				p[lg][id] = p[lg - 1][p[lg - 1][id]];
		} 
		else {
			int v, w;
			cin >> v >> w;
			
			int ansR = 0;
			li ansS = 0;
			
			while (w > 0 && a[v] > 0) {
				int u = v;
				for (int lg = LOG - 1; lg >= 0; lg--) {
					if (a[p[lg][u]] > 0)
						u = p[lg][u];
				}
				int mn = min(a[u], w);
				a[u] -= mn;
				w -= mn;
				
				ansR += mn;
				ansS += mn * 1ll * c[u];
			}
			cout << ansR << " " << ansS << endl;
		}
	}
		
	return 0;
}

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

const int LN = 20;
const int K = 12000;

int pw2[1 << LN];

vector<int> sorted_segments(const string& s)
{
 	int n = int(s.size()) - 1;
 	vector<int> res(n);
 	for(int i = 0; i < n; i++)
 		if(s[i] <= s[i + 1])
 			res[i] = 0;
 		else
 			res[i] = 1;
 	return res;
}

vector<int> prefix_sum(const vector<int>& s)
{
 	int n = s.size();
 	vector<int> p(n + 1);
 	for(int i = 0; i < n; i++)
 		p[i + 1] = p[i] + s[i];
 	return p;
}

int naiveLCP(const string& s, const string& t)
{
 	int ans = 0;
 	int n = s.size();
 	int m = t.size();
 	while(ans < n && ans < m && s[ans] == t[ans])
 		ans++;
 	return ans;
}

vector<vector<int>> build_table(const vector<int>& a)
{
	int n = a.size();
	vector<vector<int>> table(LN, vector<int>(n));
	for(int i = 0; i < n; i++)
		table[0][i] = a[i];
	for(int i = 1; i < LN; i++)
		for(int j = 0; j < n; j++)
			if(j + (1 << (i - 1)) < n)
				table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
			else
				table[i][j] = table[i - 1][j];
	return table; 	
}

struct LCP
{
 	vector<int> idx;
 	vector<vector<int>> table;

 	int query_inner(int x, int y)
 	{
 	 	if(x > y) swap(x, y);
 	 	int len = y - x;
 	 	int d = pw2[len];
 	 	return min(table[d][x], table[d][y - (1 << d)]);
 	}

 	int query(int x, int y)
 	{
 	 	return query_inner(idx[x], idx[y]);
 	}

 	LCP() {};
 	LCP(vector<string> s) 
 	{
 		int n = s.size();
		vector<pair<string, int>> t;
		for(int i = 0; i < n; i++)
		{
		 	t.push_back(make_pair(s[i], i));
	   	}
	   	sort(t.begin(), t.end());
	   	idx.resize(n);
	   	for(int i = 0; i < n; i++)
	   	{
	   		idx[t[i].second] = i;
	   	}
	   	vector<int> LCPs;
	   	for(int i = 0; i < n - 1; i++)
	   		LCPs.push_back(naiveLCP(t[i].first, t[i + 1].first));
	   	table = build_table(LCPs);		
 	};
};

const int T = int(2e7);

map<char, int> nxt[T];
int cur = 1;
int root = 0;
int cnt[T];

void clear_trie()
{
 	root = cur++;
}

int go(int x, char c)
{
 	if(!nxt[x].count(c))
 		nxt[x][c] = cur++;
 	return nxt[x][c];
}

void add(int v, const string& s, int l, int r, int n, bool sw, const vector<int>& ps)
{
	if(sw && l + r < n - 1 && ps[n - r - 1] == ps[l])
	{
		cnt[v]++;
	}
	if(sw)
	{
		if(l + r < n - 1)
			add(go(v, s[n - r - 1]), s, l, r + 1, n, sw, ps);
 	}
 	else
 	{
 		add(go(v, '$'), s, l, r, n, true, ps);
 		if(l < n - 1)
 			add(go(v, s[l]), s, l + 1, r, n, sw, ps);
 	}
}

int calc(int v, const string& s, int l, int r, int n, bool sw, const vector<vector<int>>& good)
{
	int ans = 0;
	if(sw && l + r < n - 1 && good[l][r])
	{
		ans = cnt[v];
	}
	if(sw)
	{
		if(l + r < n)
			ans += calc(go(v, s[n - r - 1]), s, l, r + 1, n, sw, good);
	}
	else
	{
	 	ans += calc(go(v, '$'), s, l, r, n, true, good);
	 	if(l < n)
	 		ans += calc(go(v, s[l]), s, l + 1, r, n, sw, good);	
	}
	return ans;
}

long long solve_short(vector<string> s, int n)
{
	long long ans = 0;
 	clear_trie();
 	sort(s.begin(), s.end());
 	for(int i = 0; i < n; i++)
 	{
 	 	string cur = s[i];
 	 	int len = cur.size();
 	 	vector<vector<int>> good(len + 1, vector<int>(len + 1));
 	 	for(int l = 0; l < len; l++)
 	 	{
 	 	 	set<char> q;
 	 	 	for(int r = l; r < len; r++)
 	 	 	{
 	 	 	 	q.insert(cur[r]);
 	 	 	 	if(cur[l] != *q.begin() && cur[r] != *q.rbegin())
 	 	 	 	{
 	 	 	 		good[l][len - r - 1] = 1;
 	 	 	 	}
 	 	 	}
 	 	}
 	 	vector<int> p = prefix_sum(sorted_segments(cur));
 	 	add(root, cur, 0, 0, len, false, p);
 	 	ans += calc(root, cur, 0, 0, len, false, good);
 	}
 	ans = n * 1ll * (n - 1) - ans;
 	return ans;
}

long long solve_long(vector<string> s, int n)
{                     
	int len = s[0].size();
 	sort(s.begin(), s.end());
 	vector<string> t = s;
 	for(int i = 0; i < n; i++)
 		reverse(t[i].begin(), t[i].end());
 	LCP ls(s);
 	LCP lt(t);
 	long long ans = 0;
 	for(int i = 0; i < n; i++)
 	{
 	 	vector<int> aux = prefix_sum(sorted_segments(s[i]));
 	 	for(int j = i + 1; j < n; j++)
 	 	{
 	 	 	int lf = ls.query(i, j);
 	 	 	int rg = lt.query(i, j);
 	 	 	if(aux[len - rg - 1] - aux[lf] == 0)
 	 	 		ans++;
 	 	 	else
 	 	 		ans += 2;
 	 	}
	}
	return ans;
}

long long solve_class(vector<string> s, int n)
{                       
	if(n <= K)
		return solve_long(s, n);
	else
		return solve_short(s, n); 	
}

vector<int> get_class(string s)
{
	vector<int> c(26);
	for(auto x : s) c[x - 'a']++;
	return c;
}

int main()
{
	pw2[1] = 0;
	for(int i = 2; i < (1 << LN); i++)
		pw2[i] = pw2[i >> 1] + 1;
	int n;
	cin >> n;
	vector<string> s(n);
	for(int i = 0; i < n; i++)   
		cin >> s[i];         
	long long ans = 0;
	map<vector<int>, vector<string>> classes;
	for(int i = 0; i < n; i++)
		classes[get_class(s[i])].push_back(s[i]);
	int cnt = 0;
	for(auto x : classes)
	{                       
	 	ans += solve_class(x.second, x.second.size());
	 	ans += cnt * 1337ll * x.second.size();
	 	cnt += x.second.size();
	}
	cout << ans << endl;
}

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

int main() {
	int t; cin >> t;
	while (t--) {
		int k; cin >> k;
		cout << 100 / gcd(100, k) << endl;
	}
	return 0;
}

#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);
    for (int &x : a) scanf("%d", &x);
    int ans = 2;
    if (is_sorted(a.begin(), a.end()))
      ans = 0;
    else if (a[0] == 1 || a[n - 1] == n)
      ans = 1;
    else if (a[0] == n && a[n - 1] == 1)
      ans = 3;
    printf("%d\n", ans);
  }
}

#include <bits/stdc++.h>

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

using namespace std;

struct bot{
	int x, d;
};

int main() {
	int t;
	cin >> t;
	forn(_, t){
		int n, m;
		scanf("%d%d", &n, &m);
		vector<bot> a(n);
		forn(i, n) scanf("%d", &a[i].x);
		forn(i, n){
			char c;
			scanf(" %c", &c);
			a[i].d = c == 'L' ? -1 : 1;
		}
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&a](int x, int y){
			return a[x].x < a[y].x;
		});
		vector<int> ans(n, -1);
		vector<vector<int>> par(2);
		for (int i : ord){
			int p = a[i].x % 2;
			if (a[i].d == -1){
				if (par[p].empty())
					par[p].push_back(i);
				else{
					int j = par[p].back();
					par[p].pop_back();
					ans[i] = ans[j] = (a[i].x - (a[j].d == 1 ? a[j].x : -a[j].x)) / 2;
				}
			}
			else{
				par[p].push_back(i);
			}
		}
		forn(p, 2){
			while (int(par[p].size()) > 1){
				int i = par[p].back();
				par[p].pop_back();
				int j = par[p].back();
				par[p].pop_back();
				ans[i] = ans[j] = (2 * m - a[i].x - (a[j].d == 1 ? a[j].x : -a[j].x)) / 2;
			}
		}
		forn(i, n){
			printf("%d ", ans[i]);
		}
		puts("");
	}
	return 0;
}

#include <bits/stdc++.h>     

using namespace std;

const int INF = int(1e9);

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++)
		cin >> a[i];
	vector<int> pos;
	for(int i = 0; i < n; i++)
		if(a[i] == 1)
			pos.push_back(i);
	int k = pos.size();
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
	dp[0][0] = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= k; j++)
		{
		 	if(dp[i][j] == INF) continue;
		 	dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
		 	if(j < k && a[i] == 0)
		 		dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(pos[j] - i));
		}
	cout << dp[n][k] << endl;
}

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

int norm(int a) {
	while (a >= MOD)
		a -= MOD;
	while (a < 0)
		a += MOD;
	return a;
}
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;
}
int inv(int a) {
	return binPow(a, MOD - 2);
}

vector< vector<int> > d;
int n, m;

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	d.resize(n, vector<int>(m));
	fore (i, 0, n) fore (j, 0, m)
		cin >> d[i][j];
	return true;
}

inline void solve() {
	int invFact = 1;
	fore (i, 1, n + 1)
		invFact = mul(invFact, i);
	invFact = inv(invFact);
	
	int E = 0;
	fore (j, 0, m) {
		vector<int> cnt(n + 1, 0);
		fore (i, 0, n)
			cnt[n + 1 - d[i][j]]++;
		
		vector<int> d(n + 1, 0);
		d[0] = 1;
		int rem = 0;
		fore (i, 0, n) {
			rem += cnt[i];
			d[i + 1] = norm(d[i + 1] + mul(d[i], rem));
			rem = max(0, rem - 1);
		}
//		cerr << d[n] << " - " << norm(1 - mul(d[n], invFact)) << endl;
		E = norm(E + 1 - mul(d[n], invFact));
	}
	cout << E << 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);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>     

using namespace std;

const int N = 543;
const long long INF = (long long)(1e18);

struct Matching
{
 	int n1, n2;
 	vector<set<int>> g;
 	vector<int> mt, used;

 	void init()
 	{
 	 	mt = vector<int>(n2, -1);
 	}

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

 	int calc()
 	{
 	 	init();
 	 	int sum = 0;
 	 	for(int i = 0; i < n1; i++)
 	 	{
 	 		used = vector<int>(n1, 0);
 	 		sum += kuhn(i);
 	 	}
 	 	return sum;
 	}

 	void remove_vertex(int v, bool right)
 	{
 	 	if(right)
 	 	{
 	 		for(int i = 0; i < n1; i++)
 	 			g[i].erase(v);
 	 	}
 	 	else
 	 		g[v].clear();
 	}

 	void add_edge(int x, int y)
 	{
 		g[x].insert(y);
 	}

 	Matching() {};
 	Matching(int n1, int n2) : n1(n1), n2(n2)
 	{
 		g.resize(n1);
 	};
};

int n, m, k;
long long dp[N][N];
int p[N][N];
vector<int> g[N];
long long x[N], y[N];

int main()
{
	cin >> n >> m >> k;
	for(int i = 0; i < m; i++)
	{
	 	int u, v;
	 	cin >> u >> v;
	 	--u;
	 	--v;
	 	g[u].push_back(v);
	}
	for(int i = 0; i < k; i++)
		cin >> x[i] >> y[i];

	Matching mt(n, n);
	for(int i = 0; i < n; i++)
		for(auto j : g[i])
			mt.add_edge(i, j);
	int cnt = mt.calc();
	int cur = cnt;
	vector<int> seq;
	while(cur > 0)
	{
		int idx = 0;
		for(int i = 0; i < n; i++)
		{
		 	Matching mt2 = mt;
		 	mt2.remove_vertex(i, false);
		 	if(mt2.calc() < cur)
		 		idx = i + 1;
		 	mt2 = mt;
		 	mt2.remove_vertex(i, true);
		 	if(mt2.calc() < cur)
		 		idx = -(i + 1);
		}
		assert(idx != 0);
		seq.push_back(idx);
		mt.remove_vertex(abs(idx) - 1, idx < 0);
		cur--;
	}	
	reverse(seq.begin(), seq.end());
	for(int i = 0; i <= k; i++)
		for(int j = 0; j <= cnt; j++)
			dp[i][j] = -INF;
	dp[0][cnt] = 0;
	for(int i = 0; i < k; i++)
		for(int j = 0; j <= cnt; j++)
		{
			if(dp[i][j] == -INF) continue;
			for(int z = 0; z <= j; z++)
			{
				if(i + 1 + z >= n) continue;
			 	int t = j - z;
			 	long long add = max(0ll, x[i] - t * y[i]);
			 	if(dp[i + 1][z] < dp[i][j] + add)
			 	{
			 	 	dp[i + 1][z] = dp[i][j] + add;
			 	 	p[i + 1][z] = j;
			 	}
			}
		}
	cur = max_element(dp[k], dp[k] + cnt + 1) - dp[k];
	vector<int> res;
	for(int i = k; i > 0; i--)
	{
		res.push_back(0);
		for(int j = p[i][cur] - 1; j >= cur; j--)
			res.push_back(seq[j]);
		cur = p[i][cur];	
	}
	reverse(res.begin(), res.end());
	cout << res.size() << endl;
	for(auto x : res) cout << x << " ";
	cout << endl;
}

Consider the minimum possible answer. Since you have to do all $$$s$$$ problems in $$$n$$$ days, you can do $$$\lfloor \frac s n \rfloor$$$ in some of them and then $$$\lceil \frac s n \rceil$$$ in the rest of the days. Thus, $$$\lceil \frac s n \rceil$$$ is the minimum possible $$$a_n$$$.

Now it would be great if the function that tells if some $$$x$$$ can be the number of problems during the last day was monotonous for all $$$x$$$ from $$$\lceil \frac s n \rceil$$$ to $$$\infty$$$. So that function first returns true for some prefix of values, then it returns false. Intuitively, it sounds monotonous: the smaller values allow a lot of freedom for the construction and the larger values fail because they require too many problems in total.

The difficulty rises from the fact we not only have to prove that, but we also have to find a way to ask the result of that function quickly.

If we didn't have to, the proof would not be too hard.

Now that we are absolutely sure that the function is monotonous, let's change our approach.

Obviously, we should try binary search on $$$x$$$. So we have the total number of problems $$$s$$$, the number of days $$$n$$$ and some fixed number of problems during the last day $$$x$$$.

Our second educated guess can be of the following kind. Given fixed $$$n$$$ and $$$x$$$, all the possible values of $$$s$$$ that can correspond to some construction are some segment of integers. That can actually be proven in the similar manner.

So we can binary search for a solution for $$$x$$$ from $$$\lceil \frac s n \rceil$$$ to $$$s$$$. $$$f(x)$$$ can be the smallest total number of problems such that there exists a distribution. Since that value is monotonous, you can look for the largest $$$x$$$ such that $$$f(x) \le s$$$.

To calculate the function you can observe that the sequence $$$x$$$, $$$\lceil \frac x 2 \rceil$$$, $$$\left\lceil \frac{\lceil \frac x 2 \rceil}{2} \right\rceil$$$, $$$\dots$$$ has only ones after $$$\log(x)$$$ values.

Overall complexity: $$$O(\log^2 s)$$$ per testcase.

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(" ").map { it.toLong() }
        val answer = a.sortedDescending().withIndex().maxOf { (it.index + 1) * it.value }
        println(answer)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        val answer = s.count { it == 'w' } + s.split("w").sumOf { it.length / 2 }
        println(answer)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(" ").map { it.toInt() }
        val p = readLine()!!.split(" ").map { it.toInt() }
        val answer = (1..n / k).maxOf { d ->
            val m = d * k
            p.subList(n - m, n - m + d).sum()
        }
        println(answer)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(" ").map { it.toInt() }
            .withIndex().sortedBy { it.value }
        var i = 0
        var j = n - 1
        val answer = ArrayList<Int>(n)
        var bc = 0
        while (i <= j) {
            if (bc >= a[i].value) {
                answer += a[i++].index
                bc = 1
            } else {
                answer += a[j--].index
                bc++
            }
        }
        println(answer.joinToString(" ") { (it + 1).toString() })
    }
}

fun main() = repeat(readLine()!!.toInt()) {
	val n = readLine()!!.toInt()
	val a = readLine()!!.split(" ").map { it.toInt() }
	val b = readLine()!!.split(" ").map { it.toInt() }
	
	var ans = -1
	var ans_shift = -1
	for (shift in 0 until n) {
		var res = 1e9.toInt()
		for(i in 0 until n)
			res = Math.min(res, Math.abs(a[i] - b[(i + shift) % n]))
		if (res > ans) {
			ans = res
			ans_shift = shift
		}
	}	

	println(IntArray(n) { (it + ans_shift) % n + 1 }.joinToString(" ")) 
}

import java.util.*

fun main() {
    val (n, k, x) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }
    var l = 0L
    var r = 10L * 1000 * 1000 * 1000
    var res = -1L

    fun can(sum : Long) : Boolean {
        var cursum = 0L
        var need = 0
        var cur = PriorityQueue<Int>(compareBy<Int> { -it })
        for (i in 0 until n) {
            cursum += a[i]
            cur.add(a[i])
            while (cur.size > x || cursum > sum) {
                cursum -= cur.first()
                cur.remove()
                need += 1
            }
            if (cur.size == x) {
                cursum = 0L
                cur.clear()
            }
        }
        return need <= k
    }

    while (l <= r) {
        val mid = (l + r) / 2
        if (can(mid)) {
            res = mid
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    println(res)
}

fun main() {
	val (n, k) = readLine()!!.split(' ').map { it.toInt() }
	val a =	readLine()!!.split(" ").map { it.toInt() }.sorted()
	
	val p = IntArray(n + 1) { 0 }
	for (i in 0 until n) p[i + 1] = p[i] + a[i]
	
	val dp = Array(n + 1) { IntArray(k + 1) { -1 } }

 	dp[0][0] = 0
 	for (i in 0 until n) {
 		for (j in 0 until k + 1) {
 			if (dp[i][j] < 0)
 				continue
 			dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j])
 			val maxx = Math.min(k - j, (n - i) / 2)
 			for (x in 1..maxx)
 				dp[i + 2 * x][j + x] = Math.max(dp[i + 2 * x][j + x], dp[i][j] + p[i + 2 * x] - p[i + x] - p[i + x] + p[i])	
 		}
 	}
 	
 	println(dp[n][k])
}

fun main() {
	val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }	
	val a = readLine()!!.split(" ").map { it.toLong() }
	val b = readLine()!!.split(" ").map { it.toLong() }
	val c = Array(n) { readLine()!!.split(" ").map { it.toLong() } }
	
	val ev = Array(n + m) {
		if (it < n)
			longArrayOf(a[it], 1L, it.toLong())
		else
			longArrayOf(b[it - n], 0L, (it - n).toLong())
	}
	
	ev.sortWith(compareBy({ it[0] }))
	
	val vals = LongArray(n + m) { 0 }
	
	for (e in 0 until n + m) {
		if (ev[e][1] == 1L) {
			val i = ev[e][2].toInt()
			vals[e] = b.indices.filter { b[it] <= ev[e][0] }.map { c[i][it] }.max()!!
		} else {
			val j = ev[e][2].toInt()
			vals[e] = a.indices.filter { a[it] <= ev[e][0] }.map { c[it][j] }.max()!!
		}
	}
	
	var ans = 1e18.toLong()
	
	for (bonus in 1 until n + m) {
		vals[bonus] += k.toLong()
		var (res, cur, mx) = LongArray(3) { 0 }
		var i = 0
		while (true) {
			while (i < n + m && ev[i][0] <= cur) {
				mx = Math.max(mx, vals[i])
				++i;
			}
			if (i == n + m) break
			val need = (ev[i][0] - cur + mx - 1) / mx
			res += need
			cur += need * mx
		}
		ans = Math.min(ans, res)
		vals[bonus] -= k.toLong()
	}

	println(ans)
}

import java.io.PrintWriter

fun main() {
	val (n, m, q) = readLine()!!.split(' ').map { it.toInt() }
	val s = Array(n) { readLine()!! }
	val c = Array(m + 1) { IntArray(n) { 0 } }
	val rc = Array(m + 1) { IntArray(n) { 0 } }
	
	for (j in m - 1 downTo 0) {
		val cur = Array(n) { intArrayOf(s[it][j].toInt(), c[j + 1][it], it) }
		cur.sortWith(compareBy({it[0]}, {it[1]}))
		for (i in 0 until n) rc[j][i] = cur[i][2]
		c[j][cur[0][2]] = 0
		for (i in 1 until n) {
			val add = if (cur[i][0] == cur[i - 1][0] && cur[i][1] == cur[i - 1][1]) 0 else 1
			c[j][cur[i][2]] = c[j][cur[i - 1][2]] + add
		}
	}
	
	val writer = PrintWriter(System.out)
	
	repeat(q) {
		val t = readLine()!!
		var ans = 0
		var j = 0
		while (j < m) {
			var (nj, L, R) = intArrayOf(j, 0, n - 1)
			while (nj < m) {
				var (l1, r1, nL) = intArrayOf(L, R, R + 1)
				while (l1 <= r1) {
					val mid = (l1 + r1) / 2
					if (s[rc[j][mid]][nj] >= t[nj]) {
						nL = mid
						r1 = mid - 1
					} else {
						l1 = mid + 1
					}
				}
				
				var (l2, r2, nR) = intArrayOf(nL, R, nL - 1)
				while (l2 <= r2) {
					val mid = (l2 + r2) / 2
					if (s[rc[j][mid]][nj] <= t[nj]) {
						nR = mid
						l2 = mid + 1
					} else {
						r2 = mid - 1
					}
				}
				
				if (nL > nR)
					break
					
				L = nL
				R = nR
				++nj
			}
			
			if (j == nj) {
				ans = 0
				break
			}
			
			ans += 1
			j = nj
		}
		
		writer.println(ans - 1)
	}
	
	writer.close()
}

fun main() {
	val MOD = 998244353
	
	fun add(x : Int, y : Int) : Int {
		return x + y - if (x + y < MOD) 0 else MOD	
	}
	
	fun mul(x : Int, y : Int) : Int {
		return (1L * x * y % MOD).toInt()
	}
	
	val inv = IntArray(60) { 0 }.also { it[0] = 1; it[1] = (MOD + 1) / 2 }
	for (i in 2 until 60) {
		inv[i] = mul(inv[i - 1], inv[1])
	}
	
	val n = readLine()!!.toInt()
	val a =	readLine()!!.split(" ").map { it.toLong() }
	val target = a.fold(0.toLong()) { res, it -> res xor it }
	val dp = Array(n) { Array(2) { IntArray(2) { 0 } } }
	
	var ans = 0
	
	val m = 1 shl (n - 1)
	for (mask in 0 until m) {
		val cur = Array(n - 1) { longArrayOf(a[it], a[it + 1]) }
		val used = BooleanArray(n - 1) { false }
		
		for (pw in 59 downTo 0) {
			for (i in 0 until n)
				for (cnt in 0 until 2)
					for (fl in 0 until 2)
						dp[i][cnt][fl] = 0
			dp[0][0][0] = 1
			for (i in 0 until n - 1) {
				for (cnt in 0 until 2) {
					for (fl in 0 until 2) {
						if (dp[i][cnt][fl] == 0)
							continue
						val (l, r) = cur[i]
						if ((l shr pw) == (r shr pw)) {
							if (!used[i] && ((mask shr i) and 1) == 1)
								continue
							val c = (l shr pw).toInt()
							val len = (cur[i][1] - cur[i][0] + 1)
							dp[i + 1][cnt xor c][fl] = add(dp[i + 1][cnt xor c][fl], mul((len % MOD).toInt(), dp[i][cnt][fl]))
						} else for (c in 0 until 2) {
							if (!used[i] && (c != (mask shr i) and 1))
								continue
							val nl = if (c == 1) 0L else l
							var nr = if (c == 1) r - (1L shl pw) else (1L shl pw) - 1
							val len = nr - nl + 1
							val nfl = if (len == (1L shl pw) && (c != ((mask shr i) and 1))) 1 else 0
							dp[i + 1][cnt xor c][fl or nfl] = add(dp[i + 1][cnt xor c][fl or nfl], mul((len % MOD).toInt(), dp[i][cnt][fl]))
						}
					}
				}
			}
			
			var cnt = ((target shr pw) and 1).toInt()
			ans = add(ans, mul(dp[n - 1][cnt][1], inv[pw]))
			if (pw == 0) 
				ans = add(ans, dp[n - 1][cnt][0])
			
			for (i in 0 until n - 1) {
				val (l, r) = cur[i]
				if ((l shr pw) == (r shr pw)) {
					val c = (l shr pw)
					cnt = cnt xor c.toInt()
					cur[i][0] -= c shl pw
					cur[i][1] -= c shl pw
				} else {
					used[i] = true
					val c = (mask shr i) and 1
					cnt = cnt xor c.toInt()
					cur[i][0] = if (c == 1) 0 else cur[i][0]
					cur[i][1] = if (c == 1) cur[i][1] - (1L shl pw) else (1L shl pw) - 1
				}
			}
			
			if (cnt != 0)
				break
		}
	}
	
	println(ans)
}

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

li n;

inline void read() {	
	cin >> n;
}

inline void solve() {
	if (n == 1 || n == 2 || n == 4) {
		cout << -1 << endl;
		return;
	}
	if (n % 3 == 0) {
		cout << n / 3 << ' ' << 0 << ' ' << 0 << endl;
	} else if (n % 3 == 1) {
		cout << (n - 7) / 3 << ' ' << 0 << ' ' << 1 << endl;
	} else {
		cout << (n - 5) / 3 << ' ' << 1 << ' ' << 0 << endl;
	}
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    cerr << setprecision(10) << fixed;
    
    int t; cin >> t;
    while(t--) {
    	read();
    	solve();
    }
 
    //cerr << "TIME: " << clock() << endl;
}

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
const int N = 200 * 1000 + 13;

int n, k;
int a[N];

inline void read() {	
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
}

inline void solve() {
	sort(a, a + n);
	reverse(a, a + n);
	li ans = 0;
	for (int i = 0; i <= k; i++) {
		ans += a[i];
	}
	cout << ans << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    cerr << setprecision(10) << fixed;
    
    int t; cin >> t;
    while(t--) {
    	read();
    	solve();
 	}
    //cerr << "TIME: " << clock() << endl;
}

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

int n;

inline void read() {	
	cin >> n;
}

inline void solve() {
	multiset<int> was;
	for (int i = 1; i <= n; i++) {
		was.insert(i);
	}
	vector<pair<int, int> > ans;
	for (int i = 0; i < n - 1; i++) {
		auto it = was.end();
		it--;
		int a = *it;
		was.erase(it);
		it = was.end();
		it--;
		int b = *it;
		was.erase(it);
		was.insert((a + b + 1) / 2);
		ans.pb(mp(a, b));
	}
	cout << *was.begin() << endl;
	for (int i = 0; i < sz(ans); i++) {
		cout << ans[i].ft << ' ' << ans[i].sc << endl;
	}	
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    cerr << setprecision(10) << fixed;
    
    int t; cin >> t;
    while(t--) {
    	read();
    	solve();
    }
    //cerr << "TIME: " << clock() << endl;
}

#include<bits/stdc++.h>

using namespace std;

char buf[200043];

int main()
{
	int t;
	scanf("%d", &t);
	for(int tc = 1; tc <= t; tc++) {
		int n;
		scanf("%d", &n);
		scanf("%s", buf);
		string s = buf;
		queue<int> q;
		int cur = 0;
		for(int i = 0; i < n; i++)
		{
		 	if(i > 0 && s[i] != s[i - 1])
		 		cur++;
		 	if(i > 0 && s[i] == s[i - 1])
		 		q.push(cur);
		}
		int deleted = 0;       
		int score = 0;
		for(int i = 0; i < n; i++)
		{
			if(q.empty())
				break;
			q.pop();
			deleted++;
			score++;
			while(!q.empty() && q.front() == i)
			{
				q.pop();
				deleted++; 	
			}
			deleted++;
			//cerr << deleted << endl;
		}
		score += (n - deleted + 1) / 2;
		printf("%d\n", score);
	}
}

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
const int N = 200 * 1000 + 13;

int n;
string s;
string revS;
vector<int> posS[30];
vector<int> posT[30];
int cnt[30];
int t[N];

inline int sum (int r) {
	int result = 0;
	for (; r >= 0; r = (r & (r+1)) - 1)
		result += t[r];
	return result;
}

inline void inc (int i, int d) {
	for (; i < n; i = (i | (i+1)))
		t[i] += d;
}

int sum (int l, int r) {
	return sum (r) - sum (l-1);
}
     
inline void read() {	
	cin >> n >> s;
}

inline void solve() {
	revS = s;
	reverse(all(revS));
	for (int i = 0; i < sz(s); i++) {
		posS[s[i] - 'a'].pb(i);
		posT[revS[i] - 'a'].pb(i);
	}
	li ans = 0;
	for (int i = 0; i < sz(revS); i++) {
		int let = revS[i] - 'a';
		int cur = posS[let][cnt[let]];
		int oldC = cur;
		cur += sum(cur, n - 1);
		int need = i;
		ans += cur - need;
		inc(oldC, 1);
		cnt[let]++;
	}
	cout << ans << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

#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 long double ld;
typedef pair<int, int> pt;

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

int n, k;
vector<int> l, r, a;

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

inline void solve() {
	vector<li> d(n + 1, INF64);
	d[0] = 0;
	
	li ans = INF64;
	fore(i, 0, n) {
		li rem = k, total = d[i];
		for (int j = i; j < n; j++) {
			li cntReloads = (max(0LL, a[j] - rem) + k - 1) / k;
			if (cntReloads > r[j] - l[j])
				break;
			
			li newRem = (rem + cntReloads * k) - a[j];
			total += a[j];
			if (j + 1 < n) {
				if (l[j] + cntReloads < l[j + 1])
					d[j + 1] = min(d[j + 1], total + newRem);
			} else
				ans = min(ans, total);
			rem = newRem;
		}
	}
	if (ans > INF64 / 2)
		ans = -1;
	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);
	
	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 li;

const int N = 18;
const int M = (1 << N);
const li INF64 = li(1e18);

int n, m;
vector<int> g[N];
li sum[N];
int need_mask[N];
li dp[N + 1][N + 1][M];
bool p[N + 1][N + 1][M];

vector<int> order;       
vector<int> used;

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

int main()
{
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
	 	int x, y, w;
	 	cin >> x >> y >> w;
	 	--x;
	 	--y;
	 	sum[x] += w;
	 	sum[y] -= w;
	 	g[x].push_back(y);
	}
	used.resize(n);
	for(int i = 0; i < n; i++)
		dfs(i, true);
	for(int i = 0; i < n; i++)
	{
	 	used = vector<int>(n, 0);
	 	dfs(i, false);
	 	for(int j = 0; j < n; j++)
	 		if(j != i && used[j] == 1)
	 			need_mask[i] |= (1 << j);		
	}
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k < (1 << n); k++)
				dp[i][j][k] = INF64;
	dp[0][0][0] = 0;
	reverse(order.begin(), order.end());
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k < (1 << n); k++)
			{
			 	if(dp[i][j][k] > INF64 / 2)
			 		continue;
			 	if(j == n)
			 	{
			 	 	if(dp[i + 1][0][k] > dp[i][j][k])
			 	 	{
			 	 	 	dp[i + 1][0][k] = dp[i][j][k];
			 	 	 	p[i + 1][0][k] = false;
			 	 	}
			 	}
			 	else
			 	{
			 		int v = order[j];
			 		li add = sum[v] * i;
			 		if(dp[i][j + 1][k] > dp[i][j][k])
			 		{
			 		 	dp[i][j + 1][k] = dp[i][j][k];
			 		 	p[i][j + 1][k] = false;
			 		}
			 		if(((k & (1 << v)) == 0) && ((need_mask[v] & k) == need_mask[v]))
			 		{
			 		 	int nk = k | (1 << v);
			 		 	if(dp[i][j + 1][nk] > dp[i][j][k] + add)
			 		 	{
			 		 	 	dp[i][j + 1][nk] = dp[i][j][k] + add;
			 		 	 	p[i][j + 1][nk] = true;
			 		 	}
				 	}
				}
			}
	vector<int> ans(n);
	int i = n;
	int j = 0;
	int k = (1 << n) - 1;
	while(i > 0 || j > 0 || k > 0)
	{
	 	if(j == 0)
	 	{
	 	 	j = n;
	 	 	i--;
	 	}
	 	else
	 	{
	 	 	if(p[i][j][k])
	 	 	{
	 	 	 	int v = order[j - 1];
	 	 	 	ans[v] = i;
	 	 	 	k ^= (1 << v);
	 		}
	 		j--;
	 	}
	}
	for(int i = 0; i < n; i++)
		cout << ans[i] << " \n"[i == n - 1];
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(" ").map { it.toInt() }
        val n1 = n / (1 + k + k * k + k * k * k)
        val n2 = n1 * k
        val n3 = n2 * k
        val n4 = n3 * k
        println("$n1 $n2 $n3 $n4")
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k1, k2) = readLine()!!.split(" ").map { it.toInt() }
        val s = readLine()!!
        var m = 0
        var prev = 0
        for (c in s) {
            if (c == '1') {
                prev = minOf(k2 - prev, k1)
                m += prev
            } else {
                prev = 0
            }
        }
        println(m)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k, x, y) = readLine()!!.split(" ").map { it.toInt() }
        val a = readLine()!!.split(" ").map { it.toInt() }.sorted()
        val maxSum = k * n.toLong()
        var sum = 0L
        var ans = 0
        var ok = true
        var i = 0
        while (i < n && sum + a[i] <= maxSum) {
            sum += a[i]
            if (ok && a[i] > k) {
                ok = false
                ans = (n - i) * x // can simply drop the rest 
            }
            i++
        }
        ans = if (ok) (n - i) * x // drop the rest
            else minOf(ans, (n - i) * x + y) // drop the rest & rearrange
        println(ans)
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, m) = readLine()!!.split(" ").map { it.toInt() }
        val e = List(m) {
            val (u, v, w) = readLine()!!.split(" ").map { it.toInt() }
            Tun(u - 1, v - 1, w)
        }
        val a = solveDungeon(n, e)
        if (a != null) {
            println("YES")
            println(a.joinToString(" "))
        } else {
            println("NO")
        }
    }
}

private class Tun(val u: Int, val v: Int, val w: Int)

private fun solveDungeon(n: Int, e: List<Tun>): IntArray? {
    val a = IntArray(n)
    for (t in e.sortedByDescending { it.w }) {
        if (a[t.u] == 0) a[t.u] = t.w
        if (a[t.v] == 0) a[t.v] = t.w
        if (t.w != minOf(a[t.u], a[t.v])) return null
    }
    return a
}

fun main() {
    val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }
    val inf = Int.MAX_VALUE - 1
    val s = IntArray(n) { inf }
    s[k - 1] = 0
    repeat(m) {
        val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
        val sx = s[x]
        val sy = s[y]
        s[x] = minOf(sx + 1, sy)
        s[y] = minOf(sy + 1, sx)
    }
    println(s.joinToString(" ") { (if (it == inf) -1 else it).toString() })
}

import kotlin.math.*

fun main() {
    val (n, m, q) = readLine()!!.split(" ").map { it.toInt() }
    val a = Array(n) { readLine()!!.split(" ").map { it.toInt() }.toIntArray() }
    val rs = LongArray(n) { i -> (0 until m).map { j -> a[i][j].toLong() }.sum() }.toDistSum()
    val cs = LongArray(m) { j -> (0 until n).map { i -> a[i][j].toLong() }.sum() }.toDistSum()
    fun ans() = rs.min()!! + cs.min()!!
    print(ans())
    repeat(q) {
        val (x1, y1, z) = readLine()!!.split(" ").map { it.toInt() }
        val (x, y) = (x1 - 1) to (y1 - 1)
        val d = (z - a[x][y]).toLong()
        for (i in 0 until n) rs[i] += abs(x - i) * d
        for (j in 0 until m) cs[j] += abs(y - j) * d
        a[x][y] = z
        print(" ${ans()}")
    }
}

private fun LongArray.toDistSum(): LongArray {
    val s = LongArray(size)
    var su = 0L
    var wsu = 0L
    var sd = 0L
    var wsd = 0L
    for (i in 0 until size) {
        sd += get(i)
        wsd += (i + 1) * get(i)
    }
    for (i in 0 until size) {
        wsd -= sd
        sd -= get(i)
        s[i] = wsu + wsd
        su += get(i)
        wsu += su
    }
    return s
}

fun main() {
    val (k, n) = readLine()!!.split(" ").map { it.toInt() }
    val p = readLine()!!.split(" ").map { it.toInt() }
    val x = readLine()!!.split(" ").map { it.toInt() }
    val c = solveCams(n, p, x)
    if (c == null) {
        println("NO")
    } else {
        println("YES")
        println("$$${c.s1} $$${c.p1}")
        println("$$${c.s2} $$${c.p2}")
    }
}

private class Cams(val s1: Int, val p1: Int, val s2: Int, val p2: Int)

private tailrec fun gcd(x: Int, y: Int): Int = if (y == 0) x else gcd(y, x % y)

private fun solveCams(n: Int, p: List<Int>, x: List<Int>): Cams? {
    fun place2(s1: Int, p1: Int): Cams? {
        val f = BooleanArray(n) { j -> (x[j] - s1) % p1 == 0 }
        val i = f.indexOf(false)
        if (i < 0) return Cams(s1, p1, s1, p1)
        val s2 = x[i]
        var j = i + 1
        while (j < n && f[j]) j++
        if (j >= n) return Cams(s1, p1, s2, p[0])
        var p2m = x[j] - s2
        while (++j < n) {
            if (!f[j]) p2m = gcd(p2m, x[j] - s2)
        }
        for (p2 in p) if (p2m % p2 == 0) {
            return Cams(s1, p1, s2, p2)
        }
        return null
    }
    fun tryPlace2(s1: Int, p1m: Int): Cams? {
        for (p1 in p) if (p1m % p1 == 0) {
            place2(s1, p1)?.let { return it }
        }
        return null
    }
    if (n == 2) return Cams(x[0], p[0], x[1], p[0])
    for (t1 in 1..2) {
        tryPlace2(x[0], x[t1] - x[0])?.let { return it }
    }
    return tryPlace2(x[1], x[2] - x[1])
}

import java.lang.AssertionError
 
private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single long
private fun readDouble() = readLn().toDouble() // single double
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readLongs() = readStrings().map { it.toLong() } // list of longs
private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles
 
private fun myAssert(x: Boolean) {
    if (!x) {
        throw AssertionError()
    }
}
 
fun main(args: Array<String>) {
    var (tt, n) = readInts()
    var lstart = IntArray(tt)
    var rstart = IntArray(tt)
    for (i in 0 until tt) {
        var (x, y) = readInts()
        lstart[i] = x
        rstart[i] = y
    }
    var l = ArrayList<Int>()
    var r = ArrayList<Int>()
    for (i in 0 until n) {
        var (x, y) = readInts()
        l.add(x)
        r.add(y)
    }
    var order = ArrayList<Int>()
    for (i in 0 until n) {
        order.add(i)
    }
    order.sortWith(compareBy({l[it] + r[it]}, {l[it]}))
    val inf = 787788789
    fun getDistance(L: Int, R: Int) : Int {
        var low = 0
        var high = n
        while (low < high) {
            var mid = (low + high) / 2
            if (l[order[mid]] + r[order[mid]] < L + R ||
                (l[order[mid]] + r[order[mid]] == L + R && l[order[mid]] < L)) {
                low = mid + 1
            } else {
                high = mid
            }
        }
        if (low < n && l[order[low]] + r[order[low]] == L + R) {
            return l[order[low]] - L
        }
        return inf
    }
    var res = IntArray(tt) {-1}
    for (qq in 0 until tt) {
        var L = lstart[qq]
        var R = rstart[qq]
        var a = getDistance(L, R - 2) + 1
        var b = getDistance(L, R)
        var c = getDistance(L + 2, R) + 1
        res[qq] = maxOf(minOf(a, b), minOf(b, c))
        if (res[qq] >= inf) {
            res[qq] = -1
        }
    }
    println(res.joinToString(" "))
}

import kotlin.math.abs

fun main() {
    val INF = 1e9.toInt()
    val INF64 = 1e18.toLong()
    val LOG = 60
    var (n, m, q, s) = readLine()!!.split(' ').map { it.toInt() }
    s--
    val a = readLine()!!.split(' ').map { it.toInt() }
    
    val summask = LongArray(1 shl n) { 0 }
    for (mask in 0 until (1 shl n)) {
        for (i in 0 until n) {
            if ((mask and (1 shl i)) > 0)
                summask[mask] += a[i].toLong()
        }
    }

    val d = Array(n) { IntArray(n) { INF } }
    for (i in 0 until m) {
        val (x, y) = readLine()!!.split(' ').map { it.toInt() }
        d[x - 1][y - 1] = 1
    }
    
    val C = readLine()!!.split(' ').map { it.toLong() }

    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n)
                d[i][j] = minOf(d[i][j], d[i][k] + d[k][j])
        }
    }

    val dp = Array(n) { Array(n) { IntArray(1 shl n) { INF } } }
    for (st in 0 until n) {
        dp[st][st][1 shl st] = 0

        for (mask in 0 until (1 shl n)) {
            for (i in 0 until n) {
                if ((mask and (1 shl i)) == 0)
                    continue
                for (j in 0 until n) {
                    if ((mask and (1 shl j)) > 0)
                        continue
                    dp[st][j][mask or (1 shl j)] =
                            minOf(dp[st][j][mask or (1 shl j)], dp[st][i][mask] + d[i][j])
                }
            }
        }
    }

    val bst = Array(n) { LongArray(n * n) { 0 } }
    for (i in 0 until n) {
        for (mask in 0 until (1 shl n)) {
            if ((mask and (1 shl i)) > 0) {
                for (j in 0 until n) {
                    if (dp[i][j][mask] != INF)
                        bst[i][dp[i][j][mask]] = maxOf(bst[i][dp[i][j][mask]], summask[mask])
                }
            }
        }
    }

    val steps = Array(LOG) { Array(n) { LongArray(n) { INF64 } } }
    for (i in 0 until n) {
        for (j in 0 until n)
            steps[0][i][j] = dp[i][j][(1 shl n) - 1].toLong()
    }

    for (t in 1 until LOG) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                for (k in 0 until n)
                    steps[t][i][j] = minOf(steps[t][i][j], steps[t - 1][i][k] + steps[t - 1][k][j])
            }
        }
    }

    for (qr in 0 until q) {
        val sum = summask[(1 shl n) - 1]
        val need = C[qr] / sum

        var cur = LongArray(n) { INF64 }
        cur[s] = 0

        for (t in 0 until LOG - 1) {
            if ((need and (1L shl t)) > 0) {
                val ncur = LongArray(n) { INF64 }
                for (i in 0 until n) {
                    for (j in 0 until n)
                        ncur[i] = minOf(ncur[i], steps[t][j][i] + cur[j])
                }
                cur = ncur
            }
        }

        var ans = INF64
        for(i in 0 until n) {
            val lft = C[qr] % sum
            for (j in 0 until n * n) {
            	if (bst[i][j] >= lft)
            		ans = minOf(ans, cur[i] + j);
            }
        }

        println(ans)
    }
}

#include <bits/stdc++.h>

using namespace std;

int a1, a2, k1, k2, n;

inline void read() {
	cin >> a1 >> a2 >> k1 >> k2 >> n;	
}

inline void solve() {
	if (k1 > k2) {
		swap(k1, k2);
		swap(a1, a2);
	}
	int minCnt = max(0, n &mdash; a1 * (k1 &mdash; 1) &mdash; a2 * (k2 &mdash; 1));
	int maxCnt = 0;
	if (n <= a1 * k1) {
		maxCnt = n / k1;
	} else {
		maxCnt = a1 + (n &mdash; a1 * k1) / k2;
    }    
    cout << minCnt << ' ' << maxCnt << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 13;

int n;
int a[N];

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

inline void solve() {
	int pos = -1;
	li ans0 = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) {
			pos = i;
		}
		if (pos != -1) {
			ans0 += pos + 1;
		}
	}	
	int cnt1 = 0, cnt2 = 0;
	int bal = 0;
	li ansP = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) {
			cnt1 = 0, cnt2 = 0, bal = 0;
			continue;
		}
		if (bal % 2 == 0) {	
			cnt1++;
		} else {
			cnt2++;
		}
		if (a[i] < 0) {
			bal++;
		}
		if (bal % 2 == 0) {
			ansP += cnt1;
		} else {
			ansP += cnt2;
		}
	}
	cout << n * 1ll * (n + 1) / 2 - ans0 - ansP << ' ' << ansP << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

#include<bits/stdc++.h>

using namespace std;

int n;
string s, t;

inline void read() {	
	cin >> n >> s >> t;
}

inline void solve() {
	vector<int> pos01, pos10;
	for (int i = 0; i < n; i++) {
		if (s[i] != t[i]) {
			if (s[i] == 'a') {
				pos01.pb(i);
			} else {
				pos10.pb(i);
			}
		}
	}
	if (sz(pos01) % 2 != sz(pos10) % 2) {
		cout << -1 << endl;
		return;
	}
	vector<pair<int, int> > ans;
	for (int i = 0; i + 1 < sz(pos01); i += 2) {
		ans.pb(mp(pos01[i], pos01[i + 1]));
	}
	for (int i = 0; i + 1 < sz(pos10); i += 2) {
		ans.pb(mp(pos10[i], pos10[i + 1]));
	}
	if (sz(pos01) % 2) {
		int x = pos01.back();
		int y = pos10.back();
		ans.pb(mp(x, x));
		ans.pb(mp(x, y));
	}
	cout << sz(ans) << endl;
	for (int i = 0; i < sz(ans); i++) {
		cout << ans[i].ft + 1 << ' ' << ans[i].sc + 1 << endl;
	}
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int n;

int main() {
    cin >> n;
    long double sum1 = 0, sum2 = 0;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] != '?') {
            if (i < n / 2) {
                sum1 += (long double)(s[i] - '0');
            } else {
                sum2 += (long double)(s[i] - '0');
            }
        } else {
            if (i < n / 2) {
                sum1 += (long double)4.5;
            } else {
                sum2 += (long double)4.5;   
            }
        }
    }
    if (fabsl(sum1 - sum2) < 1e-9) {
        cout << "Bicarp" << endl;
    } else {
        cout << "Monocarp" << endl;
    }
}

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1000 * 1000 + 13;
const int M = 20 + 1;
const long long INF = 1000 * 1000 * 1000 * 1ll * 1000 * 1000 * 1000;

int n;
long long d[(1 << M)];
long long cnt[M][M];
vector<int> col[M];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        x--;
        col[x].push_back(i);
    }
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            if (i == j) {
                continue;
            }
            if ((int)col[i].size() == 0 || (int)col[j].size() == 0) {
                continue;
            }
            int pos2 = 0;
            for (int pos1 = 0; pos1 < (int)col[i].size(); pos1++) {
                while (true) {
                    if (pos2 == (int)col[j].size() - 1 || col[j][pos2 + 1] > col[i][pos1]) {
                        break;
                    }
                    pos2++;
                }
                if (col[i][pos1] > col[j][pos2]) {
                    cnt[i][j] += pos2 + 1;
                }
            }
        }
    }

    for (int mask = 0; mask < (1 << 20); mask++) {
        d[mask] = INF;
    }
    d[0] = 0;
    for (int mask = 0; mask < (1 << 20); mask++) {
        vector<int> was;
        for (int i = 0; i < 20; i++) {
            if (mask & (1 << i)) {
                was.push_back(i);
            }
        }
        for (int i = 0; i < 20; i++) {
            if (mask & (1 << i)) {
                continue;
            }
            long long sum = 0;
            for (int j = 0; j < (int)was.size(); j++) {
                sum += cnt[was[j]][i];
            }
            int nmask = mask | (1 << i);
            d[nmask] = min(d[nmask], d[mask] + sum);
        }
    }
    cout << d[(1 << 20) - 1] << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1600043;

vector<int> g[N];
vector<int> gt[N];
int used[N];
vector<int> order;
int comp[N];
vector<int> result;
int v;

void add_edge(int v1, int v2)
{
	g[v1].push_back(v2);
	gt[v2].push_back(v1);
}

void add_disjunction(int v1, int v2)
{
	add_edge(v1 ^ 1, v2);
	add_edge(v2 ^ 1, v1);
}

void dfs1(int v)
{
	if(used[v]) return;
	used[v] = 1;
	for(auto u : g[v])
		dfs1(u);
	order.push_back(v);
}

void dfs2(int v, int cc)
{
	if(comp[v]) return;
	comp[v] = cc;
	for(auto u : gt[v])
		dfs2(u, cc);
}

bool solve2SAT()
{
	for(int i = 0; i < v * 2; i++)
		dfs1(i);
	reverse(order.begin(), order.end());
	int cc = 0;
	for(auto x : order)
	{
		if(comp[x] == 0)
		{
			cc++;
			dfs2(x, cc);
		}
	}
	for(int i = 0; i < v; i++)
	{
		if(comp[i * 2] == comp[i * 2 + 1])
			return false;
		else if(comp[i * 2] > comp[i * 2 + 1])
			result.push_back(i);
	}
	return true;
}

int main()
{
	int n, p, M, m;
	scanf("%d %d %d %d", &n, &p, &M, &m);
	v = p + M - 1;
	for(int i = 0; i < n; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		add_disjunction(x * 2, y * 2);
	}
	for(int i = 0; i < p; i++)
	{
		int l, r;
		scanf("%d %d", &l, &r);
		if(l != 1)
			add_disjunction((l - 2 + p) * 2, i * 2 + 1);
		if(r != M)
			add_disjunction((r - 1 + p) * 2 + 1, i * 2 + 1);
	}
	for(int i = 0; i < m; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		add_disjunction(x * 2 + 1, y * 2 + 1);
	}
	for(int i = 2; i <= M - 1; i++)
	{
	    int f1 = i - 2 + p;
	    int f2 = f1 + 1;
	    add_disjunction(f1 * 2, f2 * 2 + 1);
	}
	if(!solve2SAT())
	{
		puts("-1");
		return 0;
	}
	int k = 1;
	vector<int> stations;
	for(auto x : result)
		if(x < p)
			stations.push_back(x);
		else
			k = max(k, x - p + 2);
	printf("%d %d\n", int(stations.size()), k);
	for(auto x : stations)
		printf("%d ", x + 1);
	return 0;
}