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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end(), greater<int>());
    int sum = 0;
    for (auto& x : a) {
      if (sum + x <= k) sum += x;
      else break;
    }
    cout << k - sum << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    for(int _ = 0; _ < t; _++)
    {
        int n;
        scanf("%d", &n);
        vector<int> c(n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &c[i]);
            --c[i];
        }
        vector<int> cnt(n);
        for(auto x : c) cnt[x]++;
        int exactly1 = 0, morethan1 = 0;
        for(auto x : cnt)
            if (x == 1)
                exactly1++;
            else if(x > 1)
                morethan1++;
        printf("%d\n", morethan1 + (exactly1 + 1) / 2 * 2);
    }
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<int> vals;
    int sum = 0;
    for (int i = n - 1; i > 0; --i) {
      sum += (s[i] == '1' ? 1 : -1);
      if (sum > 0) vals.push_back(sum);
    }
    sort(vals.begin(), vals.end());
    int ans = 1;
    while (k > 0 && !vals.empty()) {
      k -= vals.back();
      vals.pop_back();
      ++ans;
    }
    cout << (k > 0 ? -1 : ans) << '\n';
  }
}

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

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

struct Seg {
	int l, r;

	bool operator< (const Seg &oth) const {
		if (l != oth.l)
			return l < oth.l;
		return r < oth.r;
	};
};

void solve() {
	int n;
	cin >> n;
	vector<Seg> seg(n);
	for (int i = 0; i < n; i++)
		cin >> seg[i].l >> seg[i].r;
	
	vector<int> ans(n, 0);
	for (int k = 0; k < 2; k++) {
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);

		sort(ord.begin(), ord.end(), [&seg](int i, int j){
			if (seg[i].l != seg[j].l)
				return seg[i].l < seg[j].l;
			return seg[i].r > seg[j].r;
		});

		set<int> bounds;
		for (int i : ord) {
			auto it = bounds.lower_bound(seg[i].r);
			if (it != bounds.end())
				ans[i] += *it - seg[i].r;
			bounds.insert(seg[i].r);
		}

		for (auto &s : seg) {
			s.l = -s.l;
			s.r = -s.r;
			swap(s.l, s.r);
		}
	}

	map<Seg, int> cnt;
	for (auto s: seg)
		cnt[s]++;
	for (int i = 0; i < n; i++)
		if (cnt[seg[i]] > 1)
			ans[i] = 0;
	
	for (int a : ans)
		cout << a << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int t; cin >> t;
	while (t--)
		solve();
	return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
vector<vector<int>> g;
 
struct LCA {
	vector<vector<pair<int, int>>> st;
	vector<int> pw;
 
	void build(vector<pair<int, int>> a) {
		int n = a.size();
		int lg = 32 - __builtin_clz(n);
		st.resize(lg, vector<pair<int, int>>(n));
		st[0] = a;
		for (int j = 1; j < lg; ++j) {
			for (int i = 0; i < n; ++i) {
				st[j][i] = st[j - 1][i];
				if (i + (1 << (j - 1)) < n)
					st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
			}
		}
		pw.resize(n + 1);
		for (int i = 2; i <= n; ++i)
			pw[i] = pw[i / 2] + 1;
	}
 
	vector<int> d, fst, par;
	vector<pair<int, int>> ord;
 
	int lca(int v, int u) {
		int l = fst[v], r = fst[u];
		if (l > r) swap(l, r);
		++r;
		int len = pw[r - l];
		assert(len < int(st.size()));
		return min(st[len][l], st[len][r - (1 << len)]).second;
	}
 
	void init(int v, int p = -1) {
		if (fst[v] == -1) fst[v] = ord.size();
		ord.push_back({ d[v], v });
		for (int u : g[v]) if (u != p) {
			par[u] = v;
			d[u] = d[v] + 1;
			init(u, v);
			ord.push_back({ d[v], v });
		}
	}
 
	LCA(int r = 0) {
		int n = g.size();
		d.resize(n);
		fst.assign(n, -1);
		par.assign(n, -1);
		ord.clear();
		init(r);
 
		build(ord);
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(2 * n);
	forn(i, 2 * n){
		cin >> a[i];
		--a[i];
	}
	g.resize(2 * n);
	forn(i, 2 * n - 1){
		int v, u;
		cin >> v >> u;
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	vector<int> l(n, -1), r(n, -1);
	forn(i, 2 * n){
		if (l[a[i]] == -1) l[a[i]] = i;
		else r[a[i]] = i;
	}
	vector<char> res(2 * n, 1);
	forn(rt, 2 * n) if (a[rt] == 0){
		LCA d(rt);
		vector<int> state(2 * n, 0);
		
		auto mark = [&](int v){
			while (v != -1 && state[v] != 1){
                state[v] = 1;
				v = d.par[v];
			}
		};
		auto markdel = [&](int v){
			queue<int> q;
			q.push(v);
			state[v] = -1;
			while (!q.empty()){
				int v = q.front();
				q.pop();
				mark(l[a[v]] ^ r[a[v]] ^ v);
				for (int u : g[v]) if (u != d.par[v] && state[u] == 0){
					state[u] = -1;
					q.push(u);
				}
			}
		};
		
		forn(i, n) mark(d.lca(l[i], r[i]));
		for (int i = 2 * n - 1; i >= 0; --i) if (state[i] == 0)
			markdel(i);
		vector<char> cur(2 * n, 0);
        for (int i = 0; i < 2 * n; ++i) if (state[i] == 1)
            cur[i] = 1;
        reverse(cur.begin(), cur.end());
		res = min(res, cur);
	}
	reverse(res.begin(), res.end());
	cout << count(res.begin(), res.end(), 1) << '\n';
	forn(i, 2 * n) if (res[i])
		cout << i + 1 << " ";
	cout << '\n';
	return 0;
}

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

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

const int N = 200 * 1000 + 13;
const int K = 5;

using li = long long;
using mat = array<array<li, K>, K>;

const li INF = 1e18;

int n, q;
li a[N], b[N];
mat t[4 * N];

mat init(li a, li b) {
  mat c;
  forn(i, K) forn(j, i + 1) c[j][i] = -INF;
  c[0][0] = c[2][2] = c[4][4] = 0;
  c[0][1] = c[2][3] = a + b;
  c[0][2] = c[2][4] = a + b + b;
  c[1][1] = c[3][3] = a;
  c[1][2] = c[3][4] = a + b;
  return c;
}

mat combine(mat a, mat b) {
  mat c = init(-INF, -INF);
  forn(i, K) forn(j, i + 1) forn(k, j + 1)
    c[k][i] = max(c[k][i], a[k][j] + b[j][i]);
  return c;
}

void build(int v, int l, int r) {
  if (l + 1 == r) {
    t[v] = init(a[l], b[l]);
    return;
  }
  int m = (l + r) / 2;
  build(v * 2 + 1, l, m);
  build(v * 2 + 2, m, r);
  t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
}

void upd(int v, int l, int r, int p) {
  if (l + 1 == r) {
    t[v] = init(a[l], b[l]);
    return;
  }
  int m = (l + r) / 2;
  if (p < m) upd(v * 2 + 1, l, m, p);
  else upd(v * 2 + 2, m, r, p);
  t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
}

mat get(int v, int l, int r, int L, int R) {
  if (L >= R) return init(-INF, -INF);
  if (l == L && r == R) return t[v];
  int m = (l + r) / 2;
  return combine(
    get(v * 2 + 1, l, m, L, min(m, R)),
    get(v * 2 + 2, m, r, max(m, L), R)
  );
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  forn(i, n) cin >> a[i];
  forn(i, n) cin >> b[i];
  build(0, 0, n);
  cin >> q;
  forn(_, q) {
    int t, x, y;
    cin >> t >> x >> y;
    --x;
    if (t == 1) {
      a[x] = y;
      upd(0, 0, n, x);
    } else if (t == 2) {
      b[x] = y;
      upd(0, 0, n, x);
    } else {
      auto res = get(0, 0, n, x, y);
      cout << res[0][4] << '\n';
    }
  }
}

fun main() = repeat(readln().toInt()) {
  readln().toInt()
  val a = readln().split(" ").map { it.toInt() }
  println(if (a.dropLast(1).contains(a.last() - 1)) a.last() - 1 else "Ambiguous")
}

fun main() = repeat(readln().toInt()) {
  val n = readln().toInt()
  println((listOf(1) + (n downTo 2)).joinToString(" "))
}

fun main() = repeat(readln().toInt()) {
  val a = readln().split("+")
  val ans = a.foldIndexed(0L) { i, res, s ->
    res + if (i == 0 || i == a.size - 1)
      s.toLong()
    else 
      (1 until s.length).maxOf { s.take(it).toLong() + s.drop(it).toLong() }
  }
  println(ans)
}

fun main() {
    repeat(readln().toInt()) {
        val (n, h, b) = readln().split(' ').map { it.toLong() }
        val grid = Array(2) { readln() }
        val sheepColumn = grid[0].indices.find { grid[0][it] == 'S' || grid[1][it] == 'S' }!!
        val wolvesLeft = (0..1).sumOf { grid[it].take(sheepColumn).count { it == 'W' } }
        val wolvesRight = (0..1).sumOf { grid[it].substring(sheepColumn).count { it == 'W' } }

        val ans = minOf(
            (wolvesLeft + wolvesRight) * h,
            wolvesLeft * h + 2 * b,
            wolvesRight * h + 2 * b,
            3 * b
        )
        println(ans)
    }
}

const val INF = 1e9.toInt()
const val vars = "RPS"

fun main() = repeat(readln().toInt()) {  
  val a = readln().map { vars.indexOf(it) }
  
  fun calc(a : List<Int>) : Int {
    if (a[0] != 0) return INF
    val balance = a.zipWithNext().fold(0) { s, (x, y) ->
      s + (if (x == y) 1 else 0) - (if ((x + 2) % 3 == y) 1 else 0)
    }
    return a.size + maxOf(balance, 0)
  }
  
  println(minOf(
    calc(a),
    calc(listOf(0) + a),
    calc(listOf(0, 2) + a)
   ))
}

fun main() = repeat(readln().toInt()) {  
  val n = readln().toInt()
  val a = readln().split(" ").map { it.toInt() - 1 }
  
  val prev = IntArray(n + 1) { -1 }
  val pos = IntArray(n) { -1 } 
  
  for (i in 0 until n) {
    for (j in a[i]-1..a[i]+1) {
      if (0 <= j && j < n) {
        prev[i] = maxOf(prev[i], pos[j])
      }
    }
    pos[a[i]] = i
  }
  
  val st = mutableListOf(n)
  var ans = 0L
  for (i in (n - 1) downTo 0) {
    while (st.size > 0 && prev[st.last()] >= i) {
      st.removeLast()
    }
    ans += st.last() - i
    st.add(i)
  }
  
  println(ans)
}

const val LOG = 19

fun main() = repeat(readln().toInt()) {  
  val n = readln().toInt()
  val p = readln().split(" ").map { it.toInt() - 1 }
  val ans = IntArray(n - 1) { n }
  
  fun rec(step: Int, p: List<Int>) {
    if (p.size == 1 || step == LOG) return
    for (cur in listOf(p, p.reversed())) {
      val (a, b) = cur.zipWithNext().partition { (x, y) -> x < y }
      a.forEach { (x, _) -> ans[x] = minOf(ans[x], step) }
      rec(step + 1, b.map { (x, _) -> x} + cur.last())
    }
  }
  
  rec(1, p)
  
  println(ans.joinToString(" "))
}

const val INF = 1e9.toInt()
const val B = 5

fun main() = repeat(readln().toInt()) {
  val (n, m, k) = readInts()
  val a = Array(n) { readInts() }
  
  var ans = 0
  
  for (bit in 0 until B) {
    val g = Array(n) { ArrayList<Pair<Int, Int>>() }
    for (i in 0 until n) {
      for (j in 0 until i) {
        val cnt = IntArray(4) { 0 }
        for (x in 0 until m) {
          val f = (a[i][x] shr bit) and 1
          val s = (a[j][x] shr bit) and 1
          ++cnt[f * 2 + s];
        }
        val f1 = (cnt[0] < k && cnt[3] < k)
        val f2 = (cnt[1] < k && cnt[2] < k)
        if (f1 != f2) {
          g[i].add(j to if (f2) 1 else 0)
          g[j].add(i to if (f2) 1 else 0)
        } else if (!f1) {
          return@repeat println("-1")
        }
      }
    }
    
    val color = IntArray(n) { -1 }
    val cnt = IntArray(2) { 0 }
    var ok = true
    
    fun dfs(v: Int, c: Int) {
      color[v] = c
      ++cnt[c]
      for ((u, d) in g[v]) {
        if (color[u] != -1) {
          if ((c xor d) != color[u]) {
            ok = false
          }
        } else {
          dfs(u, c xor d)
        }
      }
    }
    
    for (v in 0 until n) {
      if (color[v] != -1) continue
      cnt.fill(0)
      dfs(v, 0)
      if (!ok) return@repeat println("-1")
      ans += cnt.min() shl bit
    }
  }
  
  println(maxOf(0, ans))
}

fun readInts() = readln().split(" ").map { it.toInt() }

class Query(val t: Int, val x: Int)

class BIT(val mx: Int) {
	val f = LongArray(mx) { 0L }
	
	fun upd_pr(pos: Int, x: Int) {
		var i = pos
		while (i < mx) {
			f[i] = f[i] + x
			i = i or (i + 1)
		}
	}

	fun get_pr(pos: Int) : Long {
		var res = 0L
		var i = pos
		while (i >= 0) {
			res += f[i]
			i = (i and (i + 1)) - 1
		}
		return res
	}

	fun upd_su(pos: Int, x: Int) {
		var i = pos
		while (i >= 0) {
			f[i] = f[i] + x
			i = (i and (i + 1)) - 1
		}
	}

	fun get_su(pos: Int) : Long {
		var res = 0L
		var i = pos
		while (i < mx) {
			res += f[i]
			i = i or (i + 1)
		}
		return res
	}
}

fun main() {
	val n = readLine()!!.toInt()
	val a = readLine()!!.split(" ").map { it.toInt() }
	val q = Array(n) { Query(-1, -1) }
	for (i in 0 until n) {
		val (t, x) = readLine()!!.split(" ").map { it.toInt() }
		q[i] = Query(t, x - 1)
	}
	
	val d = IntArray(n + 1) { 0 }
	
	fun apply(coef: Int) {	
		var qs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
		for (i in 0 until n) {
			qs[0].add(Pair(i, n + 1))
		}
		
		var len = n + 1
		while (true) {
			val posq = IntArray(n) { -1 }
			val poss = IntArray(n) { -1 }
			val sv = IntArray(n) { -1 }
			val fq = BIT(n)
			val fs = BIT(n)
			
			var cntq = 0
			var cnts = 0
			val nqs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
			var j = 0
			
			var last = true
			for (l in 0 until n + 1) {
				for (it in qs[l]) {
					val i = it.first
					val r = it.second
					if (r - l == 1) {
						d[l] += coef
						continue
					}
					
					last = false
					val m = (l + r) / 2
					while (j < m) {
						val x = q[j].x
						if (q[j].t == 1) {
							posq[x] = cntq
							sv[x] = cnts
							cntq += 1
							cnts += 1
							fq.upd_pr(posq[x], a[x])
						}
						else if (q[j].t == 2){
							poss[x] = cnts
							cnts += 1
							fs.upd_su(poss[x], a[x])
						}
						else{
							fq.upd_pr(posq[x], -a[x])
							posq[x] = -1
							poss[x] = sv[x]
							fs.upd_su(poss[x], a[x])
						}
						j += 1
					}
					assert(j == m)
					if (poss[i] == -1 || posq[i] == -1) {
						nqs[m].add(Pair(i, r))
						continue
					}
					val tq = fq.get_pr(posq[i] - 1)
					val ts = fs.get_su(poss[i] + 1)
					var ok = true
					if (coef == 1) {
						ok = tq - a[i] >= ts
					}
					else {
						ok = tq + a[i] > ts
					}
					if (ok) {
						nqs[m].add(Pair(i, r))
					}
					else {
						nqs[l].add(Pair(i, m))
					}
				}
			}
			qs = nqs
			if (last) {
				break
			}
		}
		println("")
	}
	
	apply(1)
	apply(-1)
	for (i in 0 until n) {
		d[i + 1] += d[i]
	}
	val res = d.map { x -> (if (x == 0) "Yes" else "No") }
	println(res.take(res.size - 1).joinToString(separator = "\n"))
}

class Query(val t: Int, val x: Int)

class BIT(val mx: Int) {
    val f = LongArray(mx) { 0L }
    
    fun upd_pr(pos: Int, x: Int) {
        var i = pos
        while (i < mx) {
            f[i] = f[i] + x
            i = i or (i + 1)
        }
    }

    fun get_pr(pos: Int) : Long {
        var res = 0L
        var i = pos
        while (i >= 0) {
            res += f[i]
            i = (i and (i + 1)) - 1
        }
        return res
    }

    fun upd_su(pos: Int, x: Int) {
        var i = pos
        while (i >= 0) {
            f[i] = f[i] + x
            i = (i and (i + 1)) - 1
        }
    }

    fun get_su(pos: Int) : Long {
        var res = 0L
        var i = pos
        while (i < mx) {
            res += f[i]
            i = i or (i + 1)
        }
        return res
    }
}

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
    val q = Array(n) { Query(-1, -1) }
    for (i in 0 until n) {
        val (t, x) = readLine()!!.split(" ").map { it.toInt() }
        q[i] = Query(t, x - 1)
    }
    val fq = BIT(n)
    val fs = BIT(n)
    
    val d = IntArray(n + 1) { 0 }
    val posq = IntArray(n) { -1 }
    val poss = IntArray(n) { -1 }
    val sv = IntArray(n) { -1 }
    var cntq = 0
    var cnts = 0
    
    fun calc(l: Int, r: Int, coef: Int, all: ArrayList<Int>) {
        if (l == r - 1) {
            d[l] += all.size * coef
            return
        }
        
        val m = (l + r) / 2
        
        val who_chg = ArrayList<Int>()
        val idx_chg = ArrayList<Int>()
        val val_chg = ArrayList<Int>()
        val chq = ArrayList<Pair<Int, Int>>()
        val chs = ArrayList<Pair<Int, Int>>()
        
        for (i in l until m) {
            val x = q[i].x
            if (q[i].t == 1) {
                who_chg.add(0)
                idx_chg.add(x)
                val_chg.add(posq[x])
                posq[x] = cntq
                who_chg.add(2)
                idx_chg.add(x)
                val_chg.add(sv[x])
                sv[x] = cnts
                cntq += 1
                cnts += 1
                chq.add(Pair(posq[x], -a[x]))
                fq.upd_pr(posq[x], a[x])
            }
            else if (q[i].t == 2){
                who_chg.add(1)
                idx_chg.add(x)
                val_chg.add(poss[x])
                poss[x] = cnts
                cnts += 1
                chs.add(Pair(poss[x], -a[x]))
                fs.upd_su(poss[x], a[x])
            }
            else{
                chq.add(Pair(posq[x], a[x]))
                fq.upd_pr(posq[x], -a[x])
                who_chg.add(0)
                idx_chg.add(x)
                val_chg.add(posq[x])
                posq[x] = -1
                who_chg.add(1)
                idx_chg.add(x)
                val_chg.add(poss[x])
                poss[x] = sv[x]
                who_chg.add(2)
                idx_chg.add(x)
                val_chg.add(sv[x])
                sv[x] = -1
                chs.add(Pair(poss[x], -a[x]))
                fs.upd_su(poss[x], a[x])
            }
        }
    
        val tol = ArrayList<Int>()
        val tor = ArrayList<Int>()
        
        for (x in all) {
            if (poss[x] == -1 || posq[x] == -1) {
                tor.add(x)
                continue
            }
            val tq = fq.get_pr(posq[x] - 1)
            val ts = fs.get_su(poss[x] + 1)
            var ok = true
            if (coef == 1) {
                ok = tq - a[x] >= ts
            }
            else {
                ok = tq + a[x] > ts
            }
            if (ok) {
                tor.add(x)
            }
            else {
                tol.add(x)
            }
        }
    
        calc(m, r, coef, tor)
        
        who_chg.reverse()
        idx_chg.reverse()
        val_chg.reverse()
        
        for (i in 0 until who_chg.size) {
            if (who_chg[i] == 0) {
                posq[idx_chg[i]] = val_chg[i]
            }
            else if (who_chg[i] == 1) {
                poss[idx_chg[i]] = val_chg[i]
            }
            else {
                sv[idx_chg[i]] = val_chg[i]
            }
        }
        
        for (i in l until m) {
            if (q[i].t == 1) {
                cntq -= 1
                cnts -= 1
            }
            else if (q[i].t == 2){
                cnts -= 1
            }
        }

        for (it in chq) {
            fq.upd_pr(it.first, it.second)
        }
        for (it in chs) {
            fs.upd_su(it.first, it.second)
        }
        
        calc(l, m, coef, tol)
    }
    
    val all = ArrayList<Int>()
    for (i in 0 until n) {
        all.add(i)
    }
    calc(0, n + 1, 1, all)
    calc(0, n + 1, -1, all)
    for (i in 0 until n) {
        d[i + 1] += d[i]
    }
    val res = d.map { x -> (if (x == 0) "Yes" else "No") }
    println(res.take(res.size - 1).joinToString(separator = "\n"))
}

fun main() {
    val ans = IntArray(101) { Int.MAX_VALUE }
    ans[0] = 0
    for (i in ans.indices) {
        for ((d, c) in listOf(1 to 1, 3 to 0, 5 to 0)) {
            if (i + d in ans.indices) ans[i + d] = minOf(ans[i + d], ans[i] + c)
        }
    }
    repeat(readInt()) {
        println(ans[readInt()])
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        val (k, m) = readInts()
        println(maxOf(0, 2 * k - (m % (3 * k))))
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        val (n, k) = readLongs()
        println(n - k.countTrailingZeroBits())
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        readInt()
        val d = mutableListOf(mutableListOf<Long>())
        for (i in readLongs()) {
            if (i == 0L) {
                d.add(mutableListOf())
            } else {
                d.last().add(i)
            }
        }
        println(d.sumOf { l -> 2 * l.sum() - ((l.indices step 2).takeIf { l.size % 2 == 1 }?.maxOfOrNull { l[it] } ?: 0) })
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

private fun solve(): String {
    val (n, k) = readInts()
    var ans = listOf(n - 1, n)
    repeat(k - 1) {
        val min = ans.min()
        val prevStart = min - ans.size + 1
        if (prevStart <= 0) {
            return "-1"
        }
        ans = ans.zip(prevStart .. min).flatMap { (a, b) -> listOf(a, b) }.dropLast(1)
    }
    ans = (1 until ans.min()) + ans
    return ans.joinToString(" ")
}
fun main() {
    repeat(readInt()) {
        println(solve())
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

private const val MOD =  1000000007

@JvmInline
@Suppress("NOTHING_TO_INLINE")
private value class ModInt(val x: Int) {
    inline operator fun plus(other: ModInt) = ModInt((x + other.x).let { if (it >= MOD) it - MOD else it })
    inline operator fun minus(other: ModInt) = ModInt((x - other.x).let { if (it < 0) it + MOD else it })
    inline operator fun times(other: ModInt) = ModInt((x.toLong() * other.x % MOD).toInt())
    fun power(p_: Int): ModInt {
        var a = this
        var res = ModInt(1)
        var p = p_
        while (p != 0) {
            if ((p and 1) == 1) res *= a
            a *= a
            p = p shr 1
        }
        return res
    }

    inline operator fun div(other: ModInt) = this * other.inv()
    inline fun inv() = power(MOD - 2)

    companion object {
        inline fun from(x: Int) = ModInt((x % MOD + MOD) % MOD)
        inline fun from(x: Long) = ModInt(((x % MOD).toInt() + MOD) % MOD)
    }
}

@JvmInline
private value class ModIntArray(val storage:IntArray) {
    operator fun get(index: Int) = ModInt(storage[index])
    operator fun set(index: Int, value: ModInt) { storage[index] = value.x }
    val size get() = storage.size
}
private inline fun ModIntArray(n: Int, init: (Int) -> ModInt) = ModIntArray(IntArray(n) { init(it).x })

private const val COMB_MAX = 400_010

private val fs = ModIntArray(COMB_MAX) { ModInt(1) }.apply {
    for (i in 1 until size) {
        set(i, get(i - 1) * ModInt.from(i))
    }
}
private val ifs = ModIntArray(COMB_MAX) { fs[it].inv() }

private fun cnk(n: Int, k: Int) = if (n >= k) fs[n] * ifs[k] * ifs[n - k] else ModInt(0)

fun main() {
    val (n, k) = readInts()
    val ans = ModIntArray(n + 1) { ModInt(0) }

    for (diff in -n..n) {
        val ways = maxOf(0, diff - 1)
        val ll = maxOf(1, diff)
        val rr = minOf(n, n - 1 + diff)
        ans[ways] += ModInt(maxOf(0, rr - ll)) * cnk(n - diff - 1, k - 2)
    }
    for (i in 1 until n) {
        ans[i] += cnk(n - i - 1, k - 1)
    }
    for (j in 0 until n - 1) {
        ans[n - j - 1] += cnk(j, k - 1)
    }
    println(ans.storage.joinToString(" "))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

import kotlin.math.abs
import kotlin.math.sign

fun main() {
    readInts()
    val x = readInts()
    val h = readInts()
    val ord = buildList {
        for (i in x.indices.sortedBy { x[it] }) {
            while (isNotEmpty() && h[i] - h[last()] >= x[i] - x[last()]) {
                removeLast()
            }
            if (isEmpty() || h[last()] - h[i] <= x[i] - x[last()]) {
                add(i)
            }
        }
    }.map { x[it] to h[it] }

    fun nextAfter(pos: Int) = ord.binarySearch { (x, _) -> if (x >= pos) 1 else -1 }.inv()
    fun coverBy(idx: Int, pos: Int) = ord.getOrNull(idx)?.let { (x, h) -> maxOf(0, abs(x - pos) - h) } ?: Int.MAX_VALUE
    fun cover(pos: Int): Int {
        val a = nextAfter(pos)
        return minOf(coverBy(a - 1, pos), coverBy(a, pos))
    }

    fun cover2(l: Int, r: Int): Int {
        val a = nextAfter((l + r) / 2)
        return minOf(maxOf(coverBy(a, l), coverBy(a, r)), maxOf(coverBy(a - 1, l), coverBy(a - 1, r)))
    }

    val ans = List(readInt()) {
        val (l, r) = readInts()
        minOf(
            cover(l) + cover(r),
            cover2(l, r)
        )
    }
    println(ans.joinToString(" "))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

import java.math.BigInteger

fun main() = repeat(readLine()!!.toInt()) {
  val (n, hp) = readLine()!!.split(" ").let { (n, hp) -> n.toInt() to BigInteger(hp) } 
  val s = readLine()!!.split(" ").map { BigInteger(it) }
  val m = readLine()!!.toInt()
  val c = Array(m) { readLine()!!.split(" ").drop(1).map { it.toInt() - 1 } }
  val delta = Array(m) { BigInteger.ZERO }
  val minDelta = Array(m) { BigInteger.ZERO }
  for (i in 0 until m) {
    var curHP = BigInteger.ZERO
    for (id in c[i]) {
      if (id < n) {
        curHP += s[id]
        minDelta[i] = minOf(minDelta[i], curHP)
      } else {
        minDelta[i] = minOf(minDelta[i], curHP + minDelta[id - n])
        curHP += delta[id - n]
      }
    }
    delta[i] = curHP
  }
  
  fun rec(remHP : BigInteger, idCompSpell : Int) : Int {
    var curHP = remHP
    for (id in c[idCompSpell]) {
      if (id < n) {
        curHP += s[id]
        if (curHP <= BigInteger.ZERO)
          return id + 1
      } else {
        if (curHP + minDelta[id - n] <= BigInteger.ZERO)
          return rec(curHP, id - n)
        curHP += delta[id - n]
      }
    }
    return -1
  }
  
  println(rec(hp, m - 1))
}

fun readTree(n: Int) : List<BooleanArray> {
    val p = listOf(null) + readInts().map { it - 1 }
    return List(n) { a -> BooleanArray(n) { b -> a in generateSequence(b) { p[it] } } }
}
fun main() {
    val n = readInt()
    val t1 = readTree(n)
    val t2 = readTree(n)
    val masks = LongArray(n) { a ->
        (0 until n).filter { b -> a != b && t1[a][b] == t2[a][b] && t1[b][a] == t2[b][a] }.sumOf { 1L shl it }
    }
    val data = mutableMapOf<Long, Int>()
    data[0] = 0
    fun compute(mask: Long) : Int = data.getOrPut(mask) {
        val index = mask.countTrailingZeroBits()
        maxOf(compute(mask xor (1L shl index)), compute(mask and masks[index]) + 1)
    }
    println(2 * (n - compute((1L shl n) - 1)))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

const val M = 1000
const val K = 10

fun main() {  
  val (n, q) = readLine()!!.split(" ").map { it.toInt() }
  val a = readLine()!!.split(" ").map { it.toInt() }
  val b = readLine()!!.split(" ").map { it.toInt() }
  val l = IntArray(q)
  val r = IntArray(q)
  for (i in 0 until q) {
    val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1}
    l[i] = x
    r[i] = y
  }
  val s = b.scan(0, Int::plus)
  val ev = Array(n) { mutableListOf<Int>() }
  for (i in 0 until n) {
    for (j in 1 until K) {
      val x = s[i] - (a[i] + j - 1) / j + 1
      val pos = s.binarySearch { if (it < x) -1 else 1 }.inv()
      if (pos < i) ev[pos].add(i)
    }
  }
  val qr = Array(n) { mutableListOf<Int>() }
  for (i in 0 until q) qr[l[i]].add(i)
  val f = IntArray(n) { 0 }
  fun inc(i : Int) = generateSequence(i) { (it or (it + 1)).takeIf { it < n } }.forEach { ++f[it] }
  fun sum(i : Int) = generateSequence(i) { ((it and (it + 1)) - 1).takeIf { it >= 0 } }.sumOf { f[it] }
  for (i in 0 until n) inc(i)
  val ans = IntArray(q) { 0 }
  for (i in 0 until n) {
    for (j in ev[i]) inc(j)
    for (j in qr[i]) {
      var cur = b[l[j]]
      for (x in 1 until M.coerceAtMost(r[j] - l[j] + 1)) {
        ans[j] += (a[l[j] + x] + cur - 1) / cur
        cur += b[l[j] + x]
      }
      if (l[j] + M <= r[j]) ans[j] += sum(r[j]) - sum(l[j] + M - 1)
    }
  }
  println(ans.joinToString("\n"))
}

for _ in range(int(input())):
    ab = input()
    for i in range(1, len(ab)):
        if ab[i] != '0' and int(ab[:i]) < int(ab[i:]):
            print(ab[:i], ab[i:])
            break
    else:
        print(-1)

for _ in range(int(input())):
    s = input()
    cnt = [0, 0]
    for i in range(len(s)):
        cnt[int(s[i])] += 1
    for i in range(len(s) + 1):
        if (i == len(s) or cnt[1 - int(s[i])] == 0):
            print(len(s) - i)
            break
        cnt[1 - int(s[i])] -= 1

from sys import stdin, stdout

LOG = 30
cnt = [0 for i in range(LOG)]
ans = []
for _ in range(int(stdin.readline())):
    t, v = map(int, stdin.readline().split())
    if t == 1:
        cnt[v] += 1
    else:
        nw = 0
        for i in range(LOG):
            r = (v % (2 << i)) // (1 << i)
            if r > nw + cnt[i]:
                ans.append(0)
                break
            v -= r
            nw = (nw + cnt[i] - r) // 2
        else:
            ans.append(nw >= (v >> 30))
stdout.write('\n'.join(["YES" if x else "NO" for x in ans]))

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int normalize(long long x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n;
        cin >> n;
        vector <int> a(n);
        vector <int> nextMin(n);
        vector <int> dpSum(n + 2);
        vector <int> dpNext(n);
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        
        stack <int> stMin;
        nextMin[n - 1] = n;
        dpSum[n] = 1;
        for (int pos = n - 1; pos >= 0; --pos) {
            while(!stMin.empty() && a[stMin.top()] > a[pos])
                stMin.pop();
            nextMin[pos] = stMin.empty() ? n : stMin.top();
            stMin.push(pos);
            
            int nxtPos = nextMin[pos];
            int dpPos = normalize(dpSum[pos + 1] - dpSum[nxtPos + 1]);
            if (nxtPos != n) {
                dpPos = normalize(dpPos + dpNext[nxtPos]);
                dpNext[pos] = normalize(dpSum[nxtPos] - dpSum[nxtPos + 1] + dpNext[nxtPos]);
            }
            dpSum[pos] = normalize(dpPos + dpSum[pos + 1]);
            
            //cout << pos << ' ' << nxtPos << ' ' << dpPos << endl;
        }
        
        int res = 0;
        int mn = a[0];
        for(int i = 0; i < n; ++i) {
            mn = min(mn, a[i]);
            if (a[i] == mn) {
                res = normalize(res + dpSum[i] - dpSum[i + 1]);
            }
        }
        cout << res << endl;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 111;

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

vector<edge> e;
vector<int> g[N];

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

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

int n, m, s, t, v;

pair<int, long long> MCMF()
{
    int flow = 0;
    long long cost = 0;
    while(true)
    {
        vector<long long> d(v, (long long)(1e18));
        vector<int> p(v, -1);
        vector<int> pe(v, -1);
        queue<int> q;
        vector<bool> inq(v);
        q.push(s);
        inq[s] = true;
        d[s] = 0;
        while(!q.empty())
        {
            int k = q.front();
            q.pop();
            inq[k] = false;
            for(auto ei : g[k])
            {
                if(rem(ei) == 0) continue;
                int to = e[ei].y;
                int w = e[ei].w;
                if(d[to] > d[k] + w)
                {
                    d[to] = d[k] + w;
                    p[to] = k;
                    pe[to] = ei;
                    if(!inq[to])
                    {
                        inq[to] = true;
                        q.push(to);
                    }
                }
            }
        }
        if(p[t] == -1) break;
        flow++;
        cost += d[t];
        int cur = t;
        while(cur != s)
        {
            e[pe[cur]].f++;
            e[pe[cur] ^ 1].f--;
            cur = p[cur];
        }
    }
    return make_pair(flow, cost);
}

int get_sum(const vector<int>& v)
{
    int sum = 0;
    for(auto x : v) sum += x;
    return sum;
}

int main()
{
    cin >> n >> m;
    s = n + m;
    t = n + m + 1;
    v = n + m + 2;
    int sum_matrix = 0;
    vector<int> A(n), B(m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            int x;
            cin >> x;
            sum_matrix += x;
            if(x == 1)
                add_edge(i, j + n, 1, 0);
            else
                add_edge(i, j + n, 1, 1);
        }
    for(int i = 0; i < n; i++)
    {
        cin >> A[i];
        add_edge(s, i, A[i], 0);
    }
    for(int i = 0; i < m; i++) 
    {
        cin >> B[i];
        add_edge(i + n, t, B[i], 0);
    }
    
    auto res = MCMF();
    if(res.first != get_sum(A) || res.first != get_sum(B))
        cout << -1 << endl;
    else
        cout << sum_matrix - res.first + res.second * 2 << endl;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second

using namespace std;

struct sparse_table {
    vector<vector<int>> st;
    vector<int> pw;
    
    sparse_table() {}
    
    sparse_table(const vector<int> &a) {
        int n = a.size();
        int logn = 32 - __builtin_clz(n);
        st.resize(logn, vector<int>(n));
        forn(i, n)
            st[0][i] = a[i];
        for (int j = 1; j < logn; ++j) forn(i, n) {
            st[j][i] = st[j - 1][i];
            if (i + (1 << (j - 1)) < n)
                st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
        }
        pw.resize(n + 1);
        pw[0] = pw[1] = 0;
        for (int i = 2; i <= n; ++i)
            pw[i] = pw[i >> 1] + 1;
    }
    
    int get(int l, int r) {
        if (l >= r) return 1e9;
        int len = pw[r - l];
        return min(st[len][l], st[len][r - (1 << len)]);
    }
};

struct suffix_array {
    vector<int> c, pos;
    vector<pair<pair<int, int>, int>> p, nw;
    vector<int> cnt;
    int n;
    
    void radix_sort(int max_al) {
        cnt.assign(max_al, 0);
        forn(i, n) ++cnt[p[i].x.y];
        for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
        nw.resize(n);
        forn(i, n) nw[--cnt[p[i].x.y]] = p[i];
        cnt.assign(max_al, 0);
        forn(i, n) ++cnt[nw[i].x.x];
        for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i) p[--cnt[nw[i].x.x]] = nw[i];
    }
    
    vector<int> lcp;
    sparse_table st;
    
    int get_lcp(int l, int r) {
        l = c[l], r = c[r];
        if (l > r) swap(l, r);
        return st.get(l, r);
    }
    
    suffix_array(const string &s) {
        n = s.size();
        c = vector<int>(s.begin(), s.end());
        int max_al = *max_element(c.begin(), c.end()) + 1;
        p.resize(n);
        for (int k = 1; k < n; k <<= 1) {
            for (int i = 0, j = k; i < n; ++i, j = (j + 1 == n ? 0 : j + 1))
                p[i] = make_pair(make_pair(c[i], c[j]), i);
            radix_sort(max_al);
            c[p[0].y] = 0;
            for (int i = 1; i < n; ++i) c[p[i].y] = c[p[i - 1].y] + (p[i].x != p[i - 1].x);
            max_al = c[p.back().y] + 1;
        }
        lcp.resize(n);
        int l = 0;
        forn(i, n) {
            l = max(0, l - 1);
            if (c[i] == n - 1)
                continue;
            while (i + l < n && p[c[i] + 1].y + l < n && s[i + l] == s[p[c[i] + 1].y + l])
                ++l;
            lcp[c[i]] = l;
        }
        pos.resize(n);
        forn(i, n)
            pos[i] = p[i].y;
        st = sparse_table(lcp);
    }
};

int main() {
    string s;
    int n;
    cin >> n;
    cin >> s;
    string t = s;
    reverse(t.begin(), t.end());
    auto sa = suffix_array(s + "#" + t + "$");
    vector<vector<int>> ev0(n), ev1(n);
    long long base = 0;
    vector<long long> dt(n + 2);
    vector<int> d1(n);
    forn(i, n){
        int len0 = sa.get_lcp(i, 2 * n - i + 1);
        base += len0;
        dt[i - len0] += 1;
        dt[i] -= 1;
        dt[i + 1] -= 1;
        dt[i + len0 + 1] += 1;
        if (i - len0 - 1 >= 0 && i + len0 < n){
            ev0[i - len0 - 1].push_back(i);
            ev0[i + len0].push_back(i);
        }
        int len1 = sa.get_lcp(i, 2 * n - i);
        d1[i] = len1;
        dt[i - len1 + 1] += 1;
        dt[i + 1] -= 2;
        dt[i + len1 + 1] += 1;
        base += len1;
        if (i - len1 >= 0 && i + len1 < n){
            ev1[i - len1].push_back(i);
            ev1[i + len1].push_back(i);
        }
    }
    vector<long long> dx(n + 1);
    long long curt = 0, val = 0;
    forn(i, n){
        curt += dt[i];
        val += curt;
        dx[i] = val;
    }
    long long ans = base;
    int pos = -1, nc = -1;
    bool gr = false;
    forn(i, n) forn(c, 26) if (c != s[i] - 'a'){
        long long cur = base;
        for (int j : ev0[i]){
            if (j <= i && c == s[2 * j - i - 1] - 'a')
                cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 2));
            else if (j > i && c == s[2 * j - i - 1] - 'a')
                cur += 1 + sa.get_lcp(2 * j - i, 2 * n - (i - 1));
        }
        for (int j : ev1[i]){
            if (c != s[2 * j - i] - 'a') continue;
            if (j < i)
                cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 1));
            else
                cur += 1 + sa.get_lcp(2 * j - i + 1, 2 * n - (i - 1));
        }
        cur += d1[i];
        cur -= dx[i];
        bool upd = false;
        if (cur > ans){
            upd = true;
        }
        else if (cur == ans){
            if (c < s[i] - 'a'){
                if (pos == -1 || gr)
                    upd = true;
            }
            else{
                if (pos < i && gr)
                    upd = true;
            }
        }
        if (upd){
            ans = cur;
            pos = i;
            nc = c;
            gr = c > s[i] - 'a';
        }
    }
    cout << ans << endl;
    if (pos != -1) s[pos] = nc + 'a';
    cout << s << endl;
    return 0;
}

fun main() {
    repeat(readInt()) {
        println(readln().dropLastWhile { it == '0' }.dropLast(1))
    }
}

private fun readInt() = readln().toInt()

fun main() = repeat(readLine()!!.toInt()) {
  val s = readLine()!!.toCharArray()
  val x = s.indexOf('-').takeIf { it >= 0 } ?: 0
  val y = s.lastIndexOf('+').takeIf { it >= x } ?: x
  s[x] = s[y].also { s[y] = s[x] }
  val bal = s.runningFold(0) { cur, c -> cur + if (c == '-') -1 else 1 }
  println(if (bal.min() == 0) "$$${x + 1} $$${y + 1}" else "-1")
}

fun main() {
    repeat(readInt()) {
        readInt()
        val s = readln() + '.' + readln()
        println(s.split(".").sumOf { maxOf(0, it.length - 1) })
    }
}
 
private fun readInt() = readln().toInt()

private fun solve() : Boolean {
    val n = readInt()
    val a = readInts().toIntArray()
    var dropped = false
    for (i in 1 until n) {
        if (a[i] == a[i-1]) {
            a[i]++
        } else if (a[i] < a[i-1]) {
            if (dropped) return false
            dropped = true
            if (i != 1) {
                when {
                    a[i-2] > a[i] -> a[i] = a[i-1]
                    a[i-2] == a[i] -> a[i]++
                    else -> {}
                }
            }
        }
    }
    return true
}
fun main() {
    repeat(readInt()) {
        println(if (solve()) "YES" else "NO")
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() = repeat(readLine()!!.toInt()) {
  val n = readLine()!!.toInt()
  val a = readLine()!!.split(" ").map { it.toLong() }
  val b = readLine()!!.split(" ").map { it.toLong() }
  val dp = Array(3) { LongArray(3) { 0 } }
  for ((x, y) in a zip b) {
    for (i in 0..2) for (j in 0..2) {
      dp[i][j] += maxOf(
      	(if (i == 1) x else 0) + (if (j == 1) y else 0),
      	(if (i == 1) y else 0) + (if (j == 1) x else 0)
      );
    }
    for (i in 0..2) for (j in 0..2) {
      if (i < 2) dp[i + 1][j] = maxOf(dp[i + 1][j], dp[i][j]);
      if (j < 2) dp[i][j + 1] = maxOf(dp[i][j + 1], dp[i][j]);
    }
  }
  println(dp[2][2]);
}

fun best(a: List<Int>, k: Int): Long {
    val r = LongArray(4)
    var sum = 0L
    for (v in a) {
        sum += v
        r[0] = maxOf(r[0], -sum)
        r[1] = maxOf(r[1], r[0] + sum)
        r[2] = maxOf(r[2], r[1] - sum)
        r[3] = maxOf(r[3], r[2] + sum)
    }
    return r[2 * k - 1]
}

fun main() {
    repeat(readInt()) {
        readInt()
        val a = readInts()
        val b = readInts()
        val mins = a.zip(b).map { minOf(it.first, it.second) }
        val maxs = a.zip(b).map { maxOf(it.first, it.second) }
        println(maxOf(best(mins, 1) + best(maxs, 1), best(maxs, 2)))
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        val (n, k) = readInts()
        val g = List(n) { mutableListOf<Int>() }
        repeat(n - 1) {
            val (a, b) = readInts().map { it - 1 }
            g[a].add(b)
            g[b].add(a)
        }
        val size = IntArray(n)
        fun dfs(v: Int, p:Int) : Int {
            size[v] = 1 + g[v].sumOf { if (it == p) 0 else dfs(it, v) }
            return size[v]
        }
        dfs(0, 0)
        val ns = size.map { it.toLong() * (n - it) }.sortedDescending()
        println(ns.subList(0, k - 1).sum() + ns.subList(k - 1, ns.size).sum() * 2)
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readln().toInt()) {
        val n = readln().toInt()
        val t = readln().split(' ').map { it.toLong() }

        fun Long.genMoments() = List(n) { (it + 1) * this }

        val sPeriod = t[0]
        val lPeriod = t.firstOrNull { it % sPeriod != 0L }

        val sMoments = sPeriod.genMoments()
        val lMoments = lPeriod?.genMoments() ?: listOf()

        val req = sMoments.union(lMoments).sorted().take(n)
        println(if (req == t) "VALID" else "INVALID")
    }
}

private fun digitSum(a: Int) = a.toString().toCharArray().sumOf { it.digitToInt() }
private fun List<Int>.lowerBound(x: Int) = binarySearch { if (it < x) -1 else 1 }.inv()
fun main() {
    val n = readInt()
    val a = readInts()
    val pw10 = buildList<Int> {
        add(1)
        repeat(9) { add(last() * 10) }
        removeAt(0)
    }
    val d = pw10.map { p -> a.map { it % p }.sorted() }
    val ds = a.sumOf { digitSum(it) }
    println(a.map { x ->
        ds + n * digitSum(x) - 9 * pw10.indices.sumOf {
            n - d[it].lowerBound(pw10[it] - (x % pw10[it]))
        }
    }.joinToString(" "))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

val MOD = 998244353

fun main() {
	val (n, k, c) = readLine()!!.split(' ').map { it.toInt() }
	val t = readLine()!!
	val cnt = n / k + 1
	val dp = Array(2) { IntArray(cnt) {0} }
	val pw = IntArray(cnt) {1}
	dp[0][0] = 1
	for (ii in 0 until n % k) {
		val i = ii and 1
		val ni = i xor 1
		var sum = 0
		val cur = c - (t[ii].toInt() - 'a'.toInt()) - 1
		var pr = 1
		for (j in 1 until cnt) {
			pw[j] = (pw[j - 1] * (cur + 1).toLong() % MOD).toInt()
		}
		for (j in 0 until cnt) {
			sum = ((sum * cur.toLong() + pr * dp[i][j].toLong()) % MOD).toInt()
			pr = (pr * c.toLong() % MOD).toInt()
			dp[ni][j] = (sum * pw[cnt - j - 1].toLong() % MOD).toInt()
		}
	}
	var ans = 0
	for (i in 0 until cnt) {
		ans = (ans + dp[n % k % 2][i]) % MOD
	}
	for (i in 0 until n) {
		if (i % k >= n % k) {
			ans = (ans * c.toLong() % MOD).toInt()
		}
	}
	println(ans)
}

import kotlin.math.abs

fun main() {
    val n = readInt()
    val c = readInts()
    val g = List(n) { mutableListOf<Pair<Int, Int>>() }
    repeat(n - 1) {
        val (a, b, w) = readInts()
        g[a - 1].add(b - 1 to w)
        g[b - 1].add(a - 1 to w)
    }
    val size = List(2) { IntArray(n) }
    var ans = 0L
    fun dfs(v: Int, p: Int) {
        size[c[v]][v] = 1
        for ((u, w) in g[v]) {
            if (u != p) {
                dfs(u, v)
                size[0][v] += size[0][u]
                size[1][v] += size[1][u]
                ans += abs(size[0][u] - size[1][u]) * w.toLong()
            }
        }
    }
    dfs(0, 0)
    println(ans)
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

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

const int N = 109;

int t;
int n;
int s[N], e[N];
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> s[i] >> e[i];
        }
        
        bool ok = true;
        for (int i = 1; i < n; ++i) 
            if (s[i] >= s[0] && e[i] >= e[0])
                ok = false;
        
        if (!ok) {
            puts("-1");
            continue;
        }
        
        cout << s[0] << endl;
    }
    return 0;
}

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

using li = long long;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<li> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    li mnA = *min_element(a.begin(), a.end());
    li sA = accumulate(a.begin(), a.end(), 0LL);
    li mnB = *min_element(b.begin(), b.end());
    li sB = accumulate(b.begin(), b.end(), 0LL);
    li ans = min(mnA * n + sB, mnB * n + sA);
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998'244'353;

void upd(int &a, int b) {
    a = (a * 1LL * b) % MOD;
}


int t;
string s;

int main() {
	cin >> t;
	for (int tc = 0; tc < t; ++tc) {
	    cin >> s;
	    int res = 1;
	    int k = s.size();
	    int n = s.size();
	    for (int l = 0; l < n; ) {
	        int r = l + 1;
	        while(r < n && s[l] == s[r])
	            ++r;
            upd(res, r - l);
            --k;
            l = r;
	    }
	    
	    for (int i = 1; i <= k; ++i)
	        upd(res, i);
        cout << k << ' ' << res << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300005;
const int MOD = 998244353;
int n;
int a[N];

void add(int &a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
}

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

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

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    
    int res = 0;    
    for (int b = 0; b < 30; ++b) {
        int cur = 0;
        vector <int> cnt(2);
        vector <int> sumOfL(2);
        cnt[0] = 1;
        int x = 0;
        for (int i = 0; i < n; ++i) {
            x ^= ((a[i] >> b) & 1);
            int sumOfR = mul(cnt[x ^ 1], i + 1);
            add(cur, sum(sumOfR, -sumOfL[x ^ 1]));
            
            ++cnt[x];
            add(sumOfL[x], i + 1);
        }
        
        add(res, mul(1 << b, cur));
    }
    
    cout << res << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 123;

int n;
int color[N];
int countColors[N][N];
int p[N];
vector<int> g[N];
int deg[N];

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

bool tryTwoColors()
{
	int v1 = n + 1;
	int v2 = n + 2;
	for(int i = 2; i <= n; i++)
	{
		if(p[i] != 1)
		{
			add_edge(i, p[i]);
		}
	}
	for(int i = 2; i <= n; i++)
	{
		if(deg[i] == 1)
			add_edge(i, v1);
	}
	for(int i = 2; i <= n; i++)
	{
		if(p[i] != 1 && deg[p[i]] == 1)
			add_edge(i, v2);
	}
	add_edge(v1, v2);
	bool bad = false;
	for(int i = 2; i <= n + 2; i++)
		if(color[i] == 0)
		{
			color[i] = 1;
			queue<int> q;
			q.push(i);
			while(!q.empty())
			{
				int k = q.front();
				q.pop();
				for(auto y : g[k])
				{
					if(color[y] == 0)
					{
						color[y] = 3 - color[k];
						q.push(y);
					}
					else if(color[y] == color[k])
						bad = true;
				}
			}
		}
	if(bad)
		for(int i = 2; i <= n + 2; i++)
			color[i] = 0;
	return !bad;
}

void tryThreeColors()
{
	for(int i = 2; i <= n; i++)
		if(p[i] == 1)
			color[i] = 1;
		else
			color[i] = (color[p[i]] % 3) + 1;
}

int findVertex(const vector<int>& colors)
{
	int s = colors.size();
	for(int i = 2; i <= n; i++)
	{
		if(vector<int>(countColors[i], countColors[i] + s) == colors)
			return i;
	}
	return -1;
}

int main()
{
	cin >> n;
	for(int i = 2; i <= n; i++)
	{
		cin >> p[i];
		deg[p[i]]++;
	}
	
	if(*max_element(p + 2, p + n + 1) == 1)
	{
		for(int i = 2; i <= n; i++)
			color[i] = 1;
	}
	else if (!tryTwoColors())
		tryThreeColors();
	
	int colorsUsed = *max_element(color + 2, color + n + 1);
	
	cout << colorsUsed << endl;
	for(int i = 2; i <= n; i++)
	{
		cout << color[i];
		if(i == n) cout << endl;
		else cout << " ";
	}
	cout.flush();
	
	for(int i = 2; i <= n; i++)
	{
		countColors[i][color[i]]++;
		countColors[p[i]][color[i]]++;
	}
	
	while(true)
	{
		int resp;
		cin >> resp;
		if(resp == -1 || resp == 1)
			exit(0);
		vector<int> counts(colorsUsed + 1);
		for(int i = 1; i <= colorsUsed; i++)
			cin >> counts[i];
		int v = findVertex(counts);
		assert(v != -1);
		cout << color[v] << endl;
		cout.flush();
	}
}

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n;
		scanf("%d", &n);
		vector<int> h(n), a(n);
		forn(i, n) scanf("%d", &h[i]);
		forn(i, n) scanf("%d", &a[i]);
		int mxa = *max_element(a.begin(), a.end()) + 1;
		
		int l = mxa == 1 ? 0 : (__lg(mxa - 1) + 1);
		vector<vector<pair<int, int>>> st(l, vector<pair<int, int>>(mxa, make_pair(0, -1)));
		vector<vector<int>> st2(l, vector<int>(mxa));
		forn(i, n){
			if (h[i] > st[0][a[i]].first){
				st2[0][a[i]] = st[0][a[i]].first;
				st[0][a[i]] = {h[i], i};
			}
			else if (h[i] > st2[0][a[i]]){
				st2[0][a[i]] = h[i];
			}
		}
		
		auto combine = [&st, &st2](int i, int x, int y){
			int mx = max(st[i][x].first, st[i][y].first);
			if (mx == st[i][x].first)
				return max(st2[i][x], st[i][y].first);
			return max(st[i][x].first, st2[i][y]);
		};
		
		for (int j = 1; j < l; ++j) forn(i, mxa){
			if (i + (1 << (j - 1)) < mxa){
				st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
				st2[j][i] = combine(j - 1, i, i + (1 << (j - 1)));
			}
			else{
				st[j][i] = st[j - 1][i];
				st2[j][i] = st2[j - 1][i];
			}
		}
		vector<int> pw(mxa + 1);
		for (int i = 2; i <= mxa; ++i) pw[i] = pw[i / 2] + 1;
		
		auto getmx = [&st, &pw](int l, int r){
			int len = pw[r - l];
			return max(st[len][l], st[len][r - (1 << len)]);
		};
		auto getmx2 = [&st, &st2, &pw, &combine](int l, int r){
			int len = pw[r - l];
			if (st[len][l].second != st[len][r - (1 << len)].second)
				return combine(len, l, r - (1 << len));
			return max(st2[len][l], st2[len][r - (1 << len)]);
		};
		
		vector<long long> svmx(mxa), svmx2(mxa);
		vector<int> svwho(mxa, -1);
		for (int x = 1; x < mxa; ++x){
			for (int l = 1; l < mxa; l += x){
				int r = min(mxa, l + x);
				int ac = (l - 1) / x + 1;
				auto tmp = getmx(l, r);
				long long mx = tmp.first * 1ll * ac;
				int who = tmp.second;
				long long mx2 = getmx2(l, r) * 1ll * ac;
				if (who == -1) continue;
				if (mx > svmx[x]){
					svmx2[x] = svmx[x];
					svmx[x] = mx;
					svwho[x] = who;
				}
				else if (mx > svmx2[x]){
					svmx2[x] = mx;
				}
				svmx2[x] = max(svmx2[x], mx2);
			}
		}
		
		vector<long long> ans(n);
		forn(i, mxa) if (svwho[i] != -1)
			ans[svwho[i]] = max(ans[svwho[i]], svmx[i] - svmx2[i]);
		
		forn(i, n) printf("%lld ", ans[i]);
		puts("");
	}
	return 0;
}

fun main() = repeat(readLine()!!.toInt()) {
	val (b, c, h) = readLine()!!.split(' ').map { it.toInt() }
	println(minOf(b - 1, c + h) * 2 + 1)
}

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

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto &x : a) {
      cin >> x;
      x %= k;
      if (!x) x = k;
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    stable_sort(ord.begin(), ord.end(), [&](int i, int j) {
      return a[i] > a[j];
    });
    for (auto &x : ord) cout << x + 1 << ' ';
    cout << endl;
  }
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    
    vector<int> lf(n), rg(n);
    lf[0] = -1;
    for (int i = 0; i < n; ++i) {
        if (i > 0) lf[i] = lf[i - 1];
        if (s[i] == '0') lf[i] = i;
    }
    rg[n - 1] = n;
    for (int i = n - 1; i >= 0; --i) {
        if (i + 1 < n) rg[i] = rg[i + 1];
        if (s[i] == '1') rg[i] = i;
    }
    
    set<pair<int, int>> st;
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        int ll = rg[l - 1], rr = lf[r - 1];
        if (ll > rr) {
            st.insert({-1, -1});
        } else {
            st.insert({ll, rr});
        }
    }
    
    cout << st.size() << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif   
    int t;
    cin >> t;
    while (t--) solve();
}

n = int(input())
a = list(map(int, input().split()))

ans = 0
l = 0
while l < n:
    r = l + 1
    hasTwo = (a[l] == 2)
    hasMiddleZero = False
    while r < n:
        if r - 1 > l and a[r - 1] == 0:
            hasMiddleZero = True
        if a[r] == 2:
            hasTwo = True
        good = (not hasMiddleZero) and (hasTwo or a[l] != 0 or a[r] != 0)
        if not good:
            break
        r += 1
    l = r
    ans += 1
    
print(ans)

#include <bits/stdc++.h>

using namespace std;

bool comp(const pair<int, int> &a, const pair<int, int> &b){
    return a.second < b.second;
}

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> stmn, stmx;
    stmn.push_back({-1, -1});
    stmx.push_back({n, -1});
    long long ans = 0;
    int len = 0;
    set<pair<int, int>> cur;
    cur.insert({-1, 0});
    cur.insert({-1, 1});
    for (int i = 0; i < n; ++i){
        int x;
        scanf("%d", &x);
        --x;
        
        while (stmn.back().first > x){
            auto it = cur.lower_bound({stmn.back().second, 0});
            auto me = it;
            auto prv = it; --prv;
            ++it;
            len -= me->first - prv->first;
            if (it != cur.end() && it->second == 0)
                len += it->first - prv->first;
            cur.erase(me);
            stmn.pop_back();
        }
        len += i - cur.rbegin()->first;
        cur.insert({i, 0});
        stmn.push_back({x, i});
        
        while (stmx.back().first < x){
            auto it = cur.lower_bound({stmx.back().second, 1});
            auto me = it;
            auto prv = it; --prv;
            ++it;
            if (it != cur.end() && it->second == 0)
                len += me->first - prv->first;
            cur.erase(me);
            stmx.pop_back();
        }
        cur.insert({i, 1});
        stmx.push_back({x, i});
        
        ans += len;
    }
    printf("%lld\n", ans - n);
}

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

const int N = 200000;
const int NODES = 32 * N;
const int INF = int(2e9);

int n;
int a[N];
int nx[NODES][2], cnt[NODES], fn[NODES];
int nodeCount = 1;

void addInt(int x, int pos) {
    int ind = 0;
    for (int i = 29; i >= 0; --i) {
        int bit = (x >> i) & 1;
        if (nx[ind][bit] == 0) {
            nx[ind][bit] = nodeCount++;
        }
        ind = nx[ind][bit];
        ++cnt[ind];
    }
    fn[ind] = pos;
}

void addInt(int x) {
    int ind = 0;
    for (int i = 29; i >= 0; --i) {
        int bit = (x >> i) & 1;
        ind = nx[ind][bit];
        ++cnt[ind];
    }
}

void removeInt(int x) {
    int ind = 0;
    for (int i = 29; i >= 0; --i) {
        int bit = (x >> i) & 1;
        ind = nx[ind][bit];
        --cnt[ind];
    }
}

PII findXor(int x) {
    int ind = 0, res = 0;
    for (int i = 29; i >= 0; --i) {
        int bit = (x >> i) & 1;
        if (cnt[nx[ind][bit]]) {
            ind = nx[ind][bit];
        } else {
            ind = nx[ind][bit ^ 1];
            res |= 1 << i;
        }
    }
    return mp(res, fn[ind]);
}

int par[200000], ra[200000];

void dsuInit() {
    forn(i, n) par[i] = i, ra[i] = 1;
}

int dsuParent(int v) {
    if (v == par[v]) return v;
    return par[v] = dsuParent(par[v]);
}

int dsuMerge(int u, int v) {
    u = dsuParent(u);
    v = dsuParent(v);
    if (u == v) return 0;
    if (ra[u] < ra[v]) swap(u, v);
    par[v] = u;
    ra[u] += ra[v];
    return 1;
}

vector<int> v[200000];
vector<pair<int, PII> > toMerge;
vector<int> g[200000];
int color[200000];

void coloring(int x, int c){
	if(color[x] != -1) return;
	color[x] = c;
	for(auto y : g[x]) coloring(y, c ^ 1);
}

int main() {
    scanf("%d", &n);
    forn(i, n) scanf("%d", a + i);
    forn(i, n) addInt(a[i], i);
    dsuInit();
    for (int merges = 0; merges < n - 1; ) {
        forn(i, n) v[i].clear();
        forn(i, n) v[dsuParent(i)].pb(i);
        toMerge.clear();
        forn(i, n) if (!v[i].empty()) {
            for (int x : v[i]) {
                removeInt(a[x]);
            }
            pair<pair<int, int>, int> res = mp(mp(INF, INF), INF);
            for (int x : v[i]) {
                res = min(res, mp(findXor(a[x]), x));
            }
            toMerge.pb(mp(res.first.first, mp(res.second, res.first.second)));
            for (int x : v[i]) {
                addInt(a[x]);
            }
        }
        for (auto p : toMerge) {
            if (dsuMerge(p.second.first, p.second.second)) {
                ++merges;
				g[p.second.first].pb(p.second.second);
				g[p.second.second].pb(p.second.first);
            }
        }
    }
	forn(i, n) color[i] = -1;
	coloring(0, 1);
	forn(i, n) printf("%d", color[i]);
	puts("");
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		string s;
		cin >> s;
		int ans = 1;
		if(s[0] == '0') ans = 0;
		if(s[0] == '?') ans = 9;
		for(int j = 1; j < s.size(); j++)
			if(s[j] == '?')
				ans *= 10;
		cout << ans << endl;
	}
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++)
	{
		int n;
		scanf("%d", &n);
		vector<int> a(n);
		for(int i = 0; i < n; i++)
			scanf("%d", &a[i]);
		vector<int> a1(n);
		for(int i = 0; i < n; i++)
			scanf("%d", &a1[i]);
		int diffl = -1, diffr = -1;
		for(int j = 0; j < n; j++)
		{
			if(a[j] != a1[j])
			{
				diffr = j;
				if(diffl == -1)
					diffl = j;
			}
		}
		while(diffl > 0 && a1[diffl - 1] <= a1[diffl])
			diffl--;
		while(diffr < n - 1 && a1[diffr + 1] >= a1[diffr])
			diffr++;
		printf("%d %d\n", diffl + 1, diffr + 1);
	}
}

for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = n
	for x in range(26):
		c = chr(x + ord('a'))
		i = 0
		cur = 0
		while i < n:
			j = i
			while j < n and (s[j] == c) == (s[i] == c):
				j += 1
			if s[i] != c:
				cur = max(cur, j - i)
			i = j
		if cur == 0:
			ans = 0
			break
		pw = 0
		while (1 << pw) <= cur:
			pw += 1
		ans = min(ans, pw)
	print(ans)

fun main() {
    repeat(readln().toInt()) {
        val (n, k) = readln().split(' ').map { it.toInt() }
        val l = readln().split(' ').map { it.toInt() }
        val r = readln().split(' ').map { it.toInt() }

        var ans = 2e9.toInt()
        var cntShort = 0
        var lenLong = 0
        for (i in 0 until n) {
            val curLen = r[i] - l[i] + 1
            if(curLen > 1)
                lenLong += curLen
            else
                cntShort++

            if (lenLong < k) {
                if (lenLong + cntShort >= k) {
                    val cntSegs = (i + 1 - cntShort) + (k - lenLong)
                    ans = minOf(ans, r[i] + 2 * cntSegs)
                }
            }
            else {
                ans = minOf(ans, r[i] - (lenLong - k) + 2 * (i + 1 - cntShort))
                break
            }
        }
        if (ans == 2e9.toInt())
            ans = -1
        println(ans)
    }
}

#include <bits/stdc++.h>

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

const long long INF64 = 1e18;

long long dp[2][11][11][6];

int main(){
	int t;
	cin >> t;
	while (t--){
		int k;
		cin >> k;
		string s;
		cin >> s;
		int n = s.size();
		forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) forn(mv, k + 1) dp[0][balo][balc][mv] = INF64;
		dp[0][k][k][0] = 0;
		int act = 0;
		forn(ii, n){
			int i = ii & 1;
			int ni = i ^ 1;
			forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) forn(mv, k + 1)
				dp[ni][balo][balc][mv] = INF64;
			forn(mv, k + 1) forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) if (dp[i][balo][balc][mv] != INF64){
				int bal = act - balo + balc;
				if (balo >= 0 && mv < k)
					dp[i][balo - 1][balc][mv + 1] = min(dp[i][balo - 1][balc][mv + 1], dp[i][balo][balc][mv] + bal);
				if (balc >= 0 && mv < k && bal > 0)
					dp[i][balo][balc - 1][mv + 1] = min(dp[i][balo][balc - 1][mv + 1], dp[i][balo][balc][mv]);
				if (s[ii] == '('){
					dp[ni][balo][balc][mv] = min(dp[ni][balo][balc][mv], dp[i][balo][balc][mv] + bal);
					if (balo + 1 <= 2 * k)
						dp[ni][balo + 1][balc][mv] = min(dp[ni][balo + 1][balc][mv], dp[i][balo][balc][mv]);
				}
				else{
					if (bal > 0)
						dp[ni][balo][balc][mv] = min(dp[ni][balo][balc][mv], dp[i][balo][balc][mv]);
					if (balc + 1 <= 2 * k)
						dp[ni][balo][balc + 1][mv] = min(dp[ni][balo][balc + 1][mv], dp[i][balo][balc][mv]);
				}
			}
			act += (s[ii] == '(' ? 1 : -1);
		}
		printf("%lld\n", *min_element(dp[n & 1][k][k], dp[n & 1][k][k] + k + 1));
	}
}

for _ in range(int(input())):
	k = int(input())
	s = input()
	n = len(s)
	st = []
	cnt = [0 for i in range(n + 1)]
	ans = 0
	for i in range(n):
		if s[i] == '(':
			ans += len(st)
			st.append(i)
		else:
			cnt[(i - st.pop()) // 2] += 1
	for i in range(n, -1, -1):
		t = min(k, cnt[i])
		ans -= t * i
		k -= t
	print(ans)

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

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

const int MOD = 998244353;

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

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

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

int main(){
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	
	vector<int> fact(2 * n + 1), rfact(2 * n + 1);
	fact[0] = 1;
	for (int i = 1; i <= 2 * n; ++i) fact[i] = mul(fact[i - 1], i);
	rfact[2 * n] = binpow(fact[2 * n], MOD - 2);
	for (int i = 2 * n - 1; i >= 0; --i) rfact[i] = mul(rfact[i + 1], i + 1);
	auto cnk = [&](int n, int k){
		if (k < 0 || n < 0 || k > n) return 0;
		return mul(fact[n], mul(rfact[k], rfact[n - k]));
	};
	auto snb = [&](int n, int k){
		return cnk(n + k, k);
	};
	
	int pw2 = 1;
	int ans = 0;
	for (int i = m; i >= 0; --i){
		int cur = 0;
		if (n - (m - i) * 1ll * (k + 1) - i * 1ll * (2 * k + 1) >= 0)
			cur = mul(snb(n - (m - i) * (k + 1) - i * (2 * k + 1), m), mul(pw2, cnk(m, i)));
		ans = add(ans, i & 1 ? -cur : cur);
		pw2 = mul(pw2, 2);
	}
	
	printf("%d\n", ans);
}

This will most likely cause issues for authors who get their blogs downvoted for some reasons other than their blogs being trash. For example, if participants choose to downvote the announcement for a contest.

And it can be very easily abused by registering a bunch of new accounts and downvoting anyone you don't like.

I don't think it can be done in any way other than requiring a specific CF rating for posting. And if this rating limit is set too low, nothing stops the people who want to post their trash from just taking part in a contest and then posting whatever they want. But if the limit is set higher, it will make so that actual participants of CF contest will be unable to post a genuine question. upd: And, unfortunately, it's not like people with high rating don't post pure BS. So, that's a no.

Come on. I hope I don't need to explain why this will only make matters worse.

#include <bits/stdc++.h>

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

using namespace std;

int n, m, m2;
vector<vector<char>> g;

int T;
vector<int> mt;
vector<int> used;

bool try_kuhn(int v){
    if (used[v] == T)
        return false;
    used[v] = T;
    forn(u, m2) if (g[v][u] && (mt[u] == -1 || try_kuhn(mt[u]))){
        mt[u] = v;
        return true;
    }
    return false;
}

int main() {
    cin >> n >> m;
    vector<string> b(m, string(n, '0'));
    forn(i, n){
        string t;
        cin >> t;
        forn(j, m) b[j][i] = t[j];
    }
    
    vector<string> nw = b;
    sort(nw.begin(), nw.end());
    nw.resize(unique(nw.begin(), nw.end()) - nw.begin());
    m2 = nw.size();
    g.assign(m2, vector<char>(m2, 0));
    forn(i, m2) forn(j, m2) if (i != j){
        bool in = true;
        forn(k, n) in &= nw[i][k] >= nw[j][k];
        if (in) g[i][j] = 1;
    }
    
    mt.assign(m2, -1);
    used.assign(m2, -1);
    T = 0;
    int k = m2;
    forn(i, m2) if (try_kuhn(i)){
        ++T;
        --k;
    }
    
    vector<int> nxt(m2, -1);
    vector<char> st(m2, true);
    forn(i, m2) if (mt[i] != -1){
        nxt[mt[i]] = i;
        st[i] = false;
    }
    
    vector<int> gr(m2), req(m2);
    int t = 0;
    forn(i, m2) if (st[i]){
        int v = i;
        int pos = 2;
        while (v != -1){
            gr[v] = t;
            req[v] = pos;
            ++pos;
            v = nxt[v];
        }
        ++t;
    }
    assert(t == k);
    
    vector<int> num(m);
    forn(i, m) num[i] = lower_bound(nw.begin(), nw.end(), b[i]) - nw.begin();
    
    printf("%d\n", k);
    forn(i, m) printf("%d ", gr[num[i]] + 1);
    puts("");
    forn(i, m) printf("%d ", req[num[i]]);
    puts("");
    forn(i, n){
        vector<int> l(k, 1);
        forn(j, m2) if (nw[j][i] == '1')
            l[gr[j]] = max(l[gr[j]], req[j]);
        forn(j, k)
            printf("%d ", l[j]);
        puts("");
    }
    return 0;
}

for _ in range(int(input())):
    n = int(input())
    s = input()
    print('YES' if n % 3 != 2 and not False in [s[i * 3 + 1] == s[i * 3 + 2] for i in range(n // 3)] else 'NO')

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = 998244353;

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

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

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

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    
    vector<int> fact(4 * n + 1);
    fact[0] = 1;
    fore(i, 1, fact.size()) fact[i] = mul(fact[i - 1], i);
    vector<int> rfact(4 * n + 1);
    rfact.back() = binpow(fact.back(), MOD - 2);
    for (int i = int(fact.size()) - 2; i >= 0; --i)
        rfact[i] = mul(rfact[i + 1], i + 1);
    
    auto cnk = [&](int n, int k){
        return mul(fact[n], mul(rfact[k], rfact[n - k]));
    };
    
    vector<vector<int>> sv(n + 1, vector<int>(5));
    forn(i, n + 1) forn(t, 5) sv[i][t] = mul(binpow(cnk(n, i), t), rfact[t]);
    
    vector<vector<vector<int>>> dp(2, vector<vector<int>>(4 * n + 1, vector<int>(5)));
    forn(ii, n + 1){
        int i = ii & 1;
        int ni = i ^ 1;
        dp[ni] = vector<vector<int>>(4 * n + 1, vector<int>(5));
        for (int t = 1; t <= 4; ++t)
            dp[ni][ii * t][t] = mul(n - ii, sv[ii][t]);
        forn(j, k + 1) for (int p = 1; p <= 4; ++p) if (dp[i][j][p]){
            dp[ni][j][p] = add(dp[ni][j][p], dp[i][j][p]);
            for (int t = 1; p + t <= 4; ++t)
                dp[ni][j + ii * t][p + t] = add(dp[ni][j + ii * t][p + t], mul(dp[i][j][p], sv[ii][t]));
        }
    }
    
    int ans = 0;
    forn(sum, k + 1){
        ans = add(ans, mul(mul(mul(
            sum < k ? 1 : 4 * n - k, 
            dp[(n & 1) ^ 1][sum][4]), 
            mul(binpow(4 * n - sum, MOD - 2), mul(rfact[4 * n], fact[4 * n - sum]))), 
            mul(fact[4], fact[sum]))
        );
    }
    
    printf("%d\n", ans);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

#define N 200000

int a[N], n, s;

bool can(int x) {
    int l = x - 1, r = n - 1;
    while (l < r) {
        if (a[r] > s - a[l]) return false;
        ++l;
        if (l < r) {
            if (a[l] > s - a[r]) return false;
            --r;
        }
    }
    return true;
}


int main() {
    long long sum = 0;
    scanf("%d %d\n", &n, &s);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
    }

    sort(a, a + n, greater<int>());

    int l = 1, r = n;
    while (l < r) {
        int m = (l + r) >> 1;
        if (can(m)) r = m;
        else l = m + 1;
    }

    long long ans = sum + r;
    cout << ans << endl;

    return 0;
}

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

void solve() 
{
    int n, a, b;
    cin >> n >> a >> b;
    int x = (n + a - 1) / a;
    if(a > b) x = 1;
    cout << x << endl;
}

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

#include <bits/stdc++.h>

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

using namespace std;

typedef long long li;

const li INF64 = 1e18;

struct base{
    int x, w, c;
};

li area(const base &a, const base &b){
    return (a.c + b.c) * li(abs(a.x - b.x));
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<base> a(n);
    forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].c);
    sort(a.begin(), a.end(), [](const base &a, const base &b){ return a.x > b.x; });
    vector<li> dp(n, -INF64);
    li ans = 0;
    forn(i, n){
        dp[i] = max(dp[i], -a[i].w * 200ll);
        for (int j = i + 1; j < n; ++j)
            dp[j] = max(dp[j], dp[i] + area(a[i], a[j]) * k - a[j].w * 200ll);
        ans = max(ans, dp[i]);
    }
    printf("%.15Lf\n", ans / (long double)(200));
    return 0;
}

#include <bits/stdc++.h>     

using namespace std;

mt19937 rnd(42);
uniform_int_distribution<int> d(1, 2);

int ask(int t, int i)
{
    cout << t << " " << i + 1 << endl;
    int x;
    cin >> x;
    return x;
}

void giveAnswer(const string& s)
{
    cout << 0 << " " << s << endl;
    int x;
    cin >> x;
    assert(x == 1);
}

void guessOne(string& s, int i)
{
    int res = ask(1, i);
    if(res == 0)
        s[i] = '1';
    else
        s[i] = s[res - 1];
}

char inv(char c)
{
    if(c == '0') return '1';
    return '0';
}

void guessTwo(string& s, int i)
{
    if(s[1] == '0')
    {
        if(d(rnd) == 1)
        {
            int res = ask(1, i);
            if(res >= 2)
            {
                s[i] = s[res - 1];
                s[i - 1] = s[res - 2];
            }
            else if(res == 1)
            {
                s[i] = '0';
                s[i - 1] = '1';
            }
            else
            {
                s[i] = '1';
                guessOne(s, i - 1);
            }
        }
        else
        {
            int res = ask(2, i);
            if(res >= 2)
            {
                s[i] = inv(s[res - 1]);
                s[i - 1] = inv(s[res - 2]);
            }
            else if(res == 1)
            {
                s[i] = '1';
                s[i - 1] = '0';
            }
            else
            {
                s[i] = '0';
                guessOne(s, i - 1);
            }
        }
    }
    else
    {
        if(d(rnd) == 1)
        {
            int res = ask(1, i);
            if(res >= 2)
            {
                s[i] = s[res - 1];
                s[i - 1] = s[res - 2];
            }
            else if(res == 1)
            {
                s[i] = '0';
                guessOne(s, i - 1);
            }
            else
            {
                s[i] = '1';
                s[i - 1] = '1';
            }
        }
        else
        {
            int res = ask(2, i);
            if(res >= 2)
            {
                s[i] = inv(s[res - 1]);
                s[i - 1] = inv(s[res - 2]);
            }
            else if(res == 1)
            {
                s[i] = '1';
                guessOne(s, i - 1);
            }
            else
            {
                s[i] = '0';
                s[i - 1] = '0';
            }
        }
    }
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        string s(n, '0');
        for(int j = 1; j < n; j += 2)
        {
            if(j == 1) guessOne(s, j);
            else guessTwo(s, j);
        }
        if(n % 2 == 1) guessOne(s, n - 1);
        giveAnswer(s);
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (auto &x : a) cin >> x;
  vector<vector<int>> g(n);
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    g[y - 1].push_back(x - 1);
  }
    
  vector<int> ans(n, -1);
  for (int s = 0; s < n; ++s) {
    vector<int> deg(n);
    for (int i = 0; i < n; ++i) 
      for (int j : g[i]) ++deg[j];
    priority_queue<pair<int, int>> q;
    for (int v = 0; v < n; ++v)
      if (deg[v] == 0 && v != s)
        q.push({a[v], v});
    for (int i = n; i > 0; --i) {
      if (q.empty() || q.top().first < i) {
        if (deg[s] == 0 && i <= a[s])
          ans[s] = i;
        break;
      }
      int v = q.top().second;
      q.pop();
      for (int u : g[v]) {
        --deg[u];
        if (deg[u] == 0 && u != s)
          q.push({a[u], u});
      }
    }
  }
  
  for (int &x : ans) cout << x << ' ';
}
 

#include <bits/stdc++.h>

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

using namespace std;

const string al = "KQRBN";

const int INF = 1e9;

struct mv{ int dx, dy; };
struct piece{ int x, y, t; };
struct seg{ int l, r; };
struct pos{ int x, y; };

bool operator <(const pos &a, const pos &b){
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

vector<vector<mv>> mvs({
    {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}},
    {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
    {{-1, 0}, {0, 1}, {1, 0}, {0, -1}},
    {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
    {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}}
});

int main() {
    int sx, sy, fx, fy;
    cin >> sx >> sy >> fx >> fy;
    swap(sx, sy), swap(fx, fy);
    --sx, --fx;
    
    int k;
    cin >> k;
    vector<piece> a(k);
    forn(i, k){
        string t;
        cin >> t >> a[i].x >> a[i].y;
        swap(a[i].x, a[i].y);
        --a[i].x;
        a[i].t = al.find(t[0]);
    }
    
    sort(a.begin(), a.end(), [](const piece &a, const piece &b){
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    
    vector<int> base({sy, fy});
    forn(i, k) base.push_back(a[i].y);
    vector<int> ys;
    for (int y : base) for (int i = y - 16; i <= y + 16; ++i)
        ys.push_back(i);
    sort(ys.begin(), ys.end());
    ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
    
    vector<vector<char>> tk(8, vector<char>(ys.size()));
    forn(i, k){
        a[i].y = lower_bound(ys.begin(), ys.end(), a[i].y) - ys.begin();
        tk[a[i].x][a[i].y] = true;
    }
    sy = lower_bound(ys.begin(), ys.end(), sy) - ys.begin();
    fy = lower_bound(ys.begin(), ys.end(), fy) - ys.begin();
    
    vector<vector<char>> bad = tk;
    
    forn(i, k){
        int x = a[i].x, y = a[i].y;
        if (a[i].t == 0 || a[i].t == 4){
            for (auto it : mvs[a[i].t]){
                int nx = x + it.dx;
                int ny = y + it.dy;
                if (0 <= nx && nx < 8)
                    bad[nx][ny] = true;
            }
        }
        else{
            for (auto it : mvs[a[i].t]){
                for (int nx = x + it.dx, ny = y + it.dy; ; nx += it.dx, ny += it.dy){
                    if (nx < 0 || nx >= 8) break;
                    if (ny < 0 || ny >= int(ys.size())) break;
                    if (tk[nx][ny]) break;
                    bad[nx][ny] = true;
                }
            }
        }
    }
    
    vector<vector<int>> d(8, vector<int>(ys.size(), INF));
    vector<vector<pos>> p(8, vector<pos>(ys.size()));
    set<pair<int, pos>> q;
    d[sx][sy] = 0;
    q.insert({0, {sx, sy}});
    while (!q.empty()){
        int x = q.begin()->second.x;
        int y = q.begin()->second.y;
        q.erase(q.begin());
        if (x == fx && y == fy){
            cout << d[x][y] << endl;
            return 0;
        }
        for (int ny : {y - 1, y, y + 1}){
            if (ny < 0 || ny >= int(ys.size())) continue;
            int dy = max(1, abs(ys[y] - ys[ny]));
            for (int nx = max(0, x - 1); nx <= min(7, x + 1); ++nx) if (!bad[nx][ny]){
                int nd = d[x][y] + dy;
                if (d[nx][ny] > nd){
                    q.erase({d[nx][ny], {nx, ny}});
                    d[nx][ny] = nd;
                    p[nx][ny] = {x, y};
                    q.insert({d[nx][ny], {nx, ny}});
                }
            }
        }
    }
    
    cout << -1 << endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    long long total = 0;
    for(int i = 0; i < n; i++)
    {
        total += n * 1ll * (a[i] + b[i]);
        total -= a[i] * 2ll * (b.end() - lower_bound(b.begin(), b.end(), a[i]));
        total -= b[i] * 2ll * (a.end() - upper_bound(a.begin(), a.end(), b[i]));
    }
    for(int i = 0; i < n; i++)
        total -= (n - 1) * 1ll * abs(a[i] - b[i]);
    cout << total << endl;
}

#include<bits/stdc++.h>

using namespace std;

int n;
vector< vector<int> > a;

bool read() {
    if (!(cin >> n))
        return false;
    a.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    }
    return true;
}

void solve() {
    long long sum = 0;
    for (int i = 0; i < n; i++)
        sum += accumulate(a[i].begin(), a[i].end(), 0LL);
    
    int mn = a[0][n - 1];
    for (int i = 0; i < n; i++)
        mn = min(mn, a[i][n - 1 - i]);
    
    cout << sum - mn << endl;
}

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

#include <bits/stdc++.h>

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

using namespace std;

const string days[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};

int main() {
    cin.tie(0);
    iostream::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<char>> ds(n, vector<char>(7));
    forn(i, n){
        int t;
        cin >> t;
        forn(_, t){
            string s;
            cin >> s;
            ds[i][find(days, days + 7, s) - days] = true;
        }
    }
    vector<int> h(m);
    forn(i, m) cin >> h[i];
    vector<vector<int>> a(k);
    forn(i, k){
        int p;
        cin >> p;
        a[i].resize(p);
        forn(j, p){
            cin >> a[i][j];
            --a[i][j];
        }
    }
    int j = 0;
    vector<int> ans(k, -1), lst(k);
    int done = 0;
    vector<map<int, int>> cur(7);
    vector<set<int>> wk(n);
    forn(i, k) forn(j, 7) if (ds[a[i][0]][j])
        ++cur[j][a[i][0]];
    forn(i, k)
        wk[a[i][0]].insert(i);
    for (int d = 1;; ++d){
        if (j < m && h[j] == d){
            ++j;
            continue;
        }
        int wd = (d - 1) % 7;
        vector<int> now, sv;
        for (auto it : cur[wd]) now.push_back(it.first);
        for (int x : now){
            forn(i, 7){
                auto it = cur[i].find(x);
                if (it != cur[i].end()){
                    if (it->second == 1)
                        cur[i].erase(it);
                    else
                        --it->second;
                }
            }
            int y = *wk[x].begin();
            sv.push_back(y);
            wk[x].erase(wk[x].begin());
        }
        forn(i, now.size()){
            int y = sv[i];
            ++lst[y];
            if (lst[y] == int(a[y].size())){
                ans[y] = d;
                ++done;
                continue;
            }
            wk[a[y][lst[y]]].insert(y);
            forn(j, 7) if (ds[a[y][lst[y]]][j])
                ++cur[j][a[y][lst[y]]];
        }
        if (done == k) break;
    }
    forn(i, k) cout << ans[i] << " ";
    cout << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int a = 1;
    for (int g = 2; g * g <= n; ++g) {
      if (n % g == 0) {
        a = n / g;
        break;
      }
    }
    cout << a << ' ' << n - a << '\n';
  }
}
 

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int t;
  cin >> t;
  while (t--) {
    string x;
    cin >> x;
    int k;
    cin >> k;
    int n = x.size();
    vector<vector<int>> pos(10);
    for (int i = 0; i < n; ++i)
      pos[x[i] - '0'].push_back(i);
    for (int i = 0; i < 10; ++i)
      reverse(pos[i].begin(), pos[i].end());
    string ans;
    int lst = 0, len = n - k;
    for (int i = 0; i < len; ++i) {
      for (int d = (i == 0); d <= 9; ++d) {
        while (!pos[d].empty() && pos[d].back() < lst)
          pos[d].pop_back();
        if (!pos[d].empty() && pos[d].back() - lst <= k) {
          ans += d + '0';
          k -= pos[d].back() - lst;
          lst = pos[d].back() + 1;
          break;
        }
      }
    }
    cout << ans << '\n';
  }
}
 

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