t = int(input())
for i in range(t):
    l, r = map(int, input().split())
    if l * 2 > r:
        print(-1, -1)
    else:
        print(l, l * 2)

for _ in range(int(input())):
	n, k, z = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	s = 0
	mx = 0
	for t in range(z + 1):
		pos = k - 2 * t
		if pos < 0:
			continue
		mx = 0
		s = 0
		for i in range(pos + 1):
			if i < n - 1:
				mx = max(mx, a[i] + a[i + 1])
			s += a[i]
		ans = max(ans, s + mx * t)
	print(ans)

for _ in range(int(input())):
	n, k, z = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	s = 0
	mx = 0
	for i in range(k + 1):
		if i < n - 1:
			mx = max(mx, a[i] + a[i + 1])
		s += a[i]
		if i % 2 == k % 2:
			tmp = (k - i) // 2
			if tmp <= z:
				ans = max(ans, s + mx * tmp)
	print(ans)

#include <bits/stdc++.h>

using namespace std;

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

int solve(const string& s, int x, int y) {
	int res = 0;
	for (auto c : s) if (c - '0' == x) {
		++res;
		swap(x, y);
	}
	if (x != y && res % 2 == 1)
		--res;
	return res;
}

void solve() {
	string s;
	cin >> s;
	int ans = 0;
	forn(x, 10) forn(y, 10)
		ans = max(ans, solve(s, x, y));
	cout << sz(s) - ans << endl;
}

int main() {
	int T;
	cin >> T;
	while (T--) solve();
}

import kotlin.math.*

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(' ').map { it.toLong() }
        val (l1, r1) = readLine()!!.split(' ').map { it.toLong() }
        val (l2, r2) = readLine()!!.split(' ').map { it.toLong() }

        var ans = 1e18.toLong()
        if (max(l1, l2) <= min(r1, r2)) {
            val rem = max(0L, k - n * (min(r1, r2) - max(l1, l2)))
            val maxPossible = n * (abs(l1 - l2) + abs(r1 - r2))
            ans = min(rem, maxPossible) + max(0L, rem - maxPossible) * 2
        } else {
            val invest = max(l1, l2) - min(r1, r2)
            for (cntInv in 1..n) {
                var curAns = invest * cntInv
                val maxPossible = (max(r1, r2) - min(l1, l2)) * cntInv
                curAns += min(k, maxPossible) + max(0L, k - maxPossible) * 2
                ans = min(ans, curAns)
            }
        }
        println(ans)
    }
}

fun gcd(a: Long, b: Long): Long {
	if (a == 0L) return b
	return gcd(b % a, a)
}

fun main() {
	repeat(readLine()!!.toInt()) {
		val (m, d, w) = readLine()!!.split(' ').map { it.toLong() }
		val w2 = w / gcd(d - 1, w)
		val mn = minOf(m, d)
		var cnt = mn / w2
		println((2 * (mn - w2) - w2 * (cnt - 1)) * cnt / 2)
	}
}

#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

const int N = 200 * 1000;

int n;
int l[N], r[N], t[N];
set<pt> st[2];

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d%d%d", &l[i], &r[i], &t[i]), --t[i];
	
	vector<pair<int, pt>> ev;
	forn(i, n) {
		ev.pb(mp(l[i], mp(0, i)));
		ev.pb(mp(r[i], mp(1, i)));
	}

	sort(all(ev));
	
	int ans = 0;
	for (auto it : ev) {
		int i = it.y.y;
		if (it.y.x) {
			int j = t[i];
			int k = j ^ 1;
			if (st[j].count(mp(r[i], i)) && !st[k].empty()) {
				++ans;
				st[k].erase(st[k].begin());
			}
			if (st[j].count(mp(r[i], i))) st[t[i]].erase(mp(r[i], i));
		} else {
			st[t[i]].insert(mp(r[i], i));
		}
	}
	
	printf("%d\n", n - ans);
}

#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

const int INF = 1e9;
const int N = 200 * 1000;

int n;
vector<pt> a[2];

struct segtree {
	int n;
	vector<int> t, ps;
	segtree(int n) : n(n) {
		t.resize(4 * n, -INF);
		ps.resize(4 * n, 0);
	}
	
	void push(int v, int l, int r) {
		if (l + 1 != r) {
			ps[v * 2 + 1] += ps[v];
			ps[v * 2 + 2] += ps[v];
		}
		t[v] += ps[v];
		ps[v] = 0;
	}
	
	void upd(int v, int l, int r, int pos, int val) {
		push(v, l, r);
		if (l + 1 == r) {
			t[v] = val;
			return;
		}
		int m = (l + r) >> 1;
		if (pos < m) upd(v * 2 + 1, l, m, pos, val);
		else upd(v * 2 + 2, m, r, pos, val);
		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	void add(int v, int l, int r, int L, int R, int val) {
		push(v, l, r);
		if (L >= R) return;
		if (l == L && r == R) {
			ps[v] += val;
			push(v, l, r);
			return;
		}
		int m = (l + r) >> 1;
		add(v * 2 + 1, l, m, L, min(m, R), val);
		add(v * 2 + 2, m, r, max(m, L), R, val);
		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	int get(int v, int l, int r, int L, int R) {
		push(v, l, r);
		if (L >= R) return -INF;
		if (l == L && r == R) 
			return t[v];
		int m = (l + r) >> 1;
		int r1 = get(v * 2 + 1, l, m, L, min(m, R));
		int r2 = get(v * 2 + 2, m, r, max(m, L), R);
		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
		return max(r1, r2);
	}
	
	void upd(int pos, int val) {
		return upd(0, 0, n, pos, val);
	}
	
	void add(int l, int r, int val) {
		return add(0, 0, n, l, r, val);
	}
	
	int get(int l, int r) {
		return get(0, 0, n, l, r);
	}
};

int main() {
	scanf("%d", &n);
	forn(i, n) {
		int l, r, t;
		scanf("%d%d%d", &l, &r, &t);
		a[t - 1].pb(mp(r, l));
	}
	
	forn(i, 2) sort(all(a[i]), [](pt a, pt b) {
		if (a.x == b.x) return a.y > b.y;
		return a.x < b.x;
	});
	
	segtree t1(sz(a[0]) + 1), t2(sz(a[1]) + 1);
	t1.upd(0, 0);
	t2.upd(0, 0);
		
	int ans = 0;
	for (int i = 0, j = 0; i + j < n; ) {
		if (i < sz(a[0]) && (j == sz(a[1]) || a[0][i].x <= a[1][j].x)) {
			int pos = upper_bound(all(a[1]), mp(a[0][i].y, -INF)) - a[1].begin() + 1; 
			int cur = t2.get(0, pos) + 1;
			ans = max(ans, cur);
			t1.upd(i + 1, cur);
			t2.add(0, pos, 1);
			++i;
		} else {
			int pos = upper_bound(all(a[0]), mp(a[1][j].y, -INF)) - a[0].begin() + 1; 
			int cur = t1.get(0, pos) + 1;
			ans = max(ans, cur);
			t2.upd(j + 1, cur);
			t1.add(0, pos, 1);
			++j;
		}
	}
	
	printf("%d\n", ans);
}

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const int N = 300043;

bool is_bridge[N];
int w[N];
int c[N];
int v[N];
vector<pair<int, int> > g[N];

vector<pair<int, int> > g2[N];
int comp[N];
li sum[N];
li dp[N];
int cnt[N];
int fup[N];
int tin[N];
int T = 0;
li ans[N];
int v1[N], v2[N];

int n, m, k;

int dfs1(int x, int e)
{
	tin[x] = T++;
	fup[x] = tin[x];
	for(auto p : g[x])
	{
		int y = p.first;
		int i = p.second;
		if(i == e)
			continue;
		if(tin[y] != -1)
			fup[x] = min(fup[x], tin[y]);
		else
		{
			fup[x] = min(fup[x], dfs1(y, i));
			if(fup[y] > tin[x])
				is_bridge[i] = true;
		}
	}
	return fup[x];
}

void dfs2(int x, int cc)
{
	if(comp[x] != -1)
		return;
	comp[x] = cc;
	cnt[cc] += v[x];
	sum[cc] += c[x];
	for(auto y : g[x])
		if(!is_bridge[y.second])
			dfs2(y.first, cc);
}

void process_edge(int x, int y, int m, int weight)
{
	li add_dp = dp[y];
	if(cnt[y] > 0 && cnt[y] < k)
		add_dp = max(0ll, add_dp - weight);
	
	cnt[x] += m * cnt[y];
	dp[x] += m * add_dp;
}

void link(int x, int y, int weight)
{
	process_edge(x, y, 1, weight);
}

void cut(int x, int y, int weight)
{
	process_edge(x, y, -1, weight);
}

void dfs3(int x, int p)
{
    dp[x] = sum[x];
	for(auto e : g2[x])
	{
		int i = e.second;
		int y = e.first;
		if(y == p)
			continue;
		dfs3(y, x);
		link(x, y, w[i]);
	}
}

void dfs4(int x, int p)
{
	ans[x] = dp[x];
	for(auto e : g2[x])
	{
		int i = e.second;
		int y = e.first;
		if(y == p)
			continue;
		cut(x, y, w[i]);
		link(y, x, w[i]);
		dfs4(y, x);
		cut(y, x, w[i]);
		link(x, y, w[i]);
	}
}

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	for(int  i = 0; i < k; i++)
	{
		int x;
		scanf("%d", &x);
		--x;
		v[x] = 1;
	}
	for(int i = 0; i < n; i++)
		scanf("%d", &c[i]);
	for(int i = 0; i < m; i++)
		scanf("%d", &w[i]);
	for(int i = 0; i < m; i++)
	{
		scanf("%d %d", &v1[i], &v2[i]);
		--v1[i];
		--v2[i];
		g[v1[i]].push_back(make_pair(v2[i], i));
		g[v2[i]].push_back(make_pair(v1[i], i));
	}
	
	for(int i = 0; i < n; i++)
	{
		tin[i] = -1;
		comp[i] = -1;
	}
	dfs1(0, -1);
	int cc = 0;
	for(int i = 0; i < n; i++)
		if(comp[i] == -1)
			dfs2(i, cc++);
	for(int i = 0; i < m; i++)
		if(is_bridge[i])
		{
			g2[comp[v1[i]]].push_back(make_pair(comp[v2[i]], i));
			g2[comp[v2[i]]].push_back(make_pair(comp[v1[i]], i));
		}
	dfs3(0, 0);
	dfs4(0, 0);
	for(int i = 0; i < n; i++)
		printf("%lld ", ans[comp[i]]);
	puts("");
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

int n;
int a[N];

void solve() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 1; i < n - 1; ++i) {
		if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
			cout << "YES" << endl;
			cout << i << ' ' << i + 1 << ' ' << i + 2 << endl;
			return;
		}
	}
	cout << "NO" << endl;
}

int main() {
	int T;
	cin >> T;
	while (T--)
		solve();
}

fun main() {
    val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S')
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        val maxCnt = s.groupingBy { it }.eachCount().maxBy { it.value }!!.key
        println("${winBy[maxCnt]}".repeat(s.length))
    }
}

for _ in range(int(input())):
    n, x = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    res, cur = 0, 1
    for s in a:
        if s * cur >= x:
            res += 1
            cur = 0
        cur += 1
    print(res)
    

#include <bits/stdc++.h>

using namespace std;

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

int n, m;
long long x, k, y;
int a[N];
int b[N];

bool upd(int l, int r, long long &res) {
    if (l > r) return true;
    bool canDel = false;
    int mx = *max_element(a + l, a + r + 1);
    int len = r - l + 1;
    if (l - 1 >= 0 && a[l - 1] > mx) canDel = true;
    if (r + 1 < n && a[r + 1] > mx) canDel = true;
    if (len < k && !canDel) return false;
    
    int need = len % k;
    res += need * y;
    len -= need;
    
    if (y * k >= x) {
        res += len / k * x;
    } else if(canDel) {
        res += len * y;
    } else {
        res += (len - k) * y + x;
    }
    
    return true;
}

int main(){
    scanf("%d %d", &n, &m);
    scanf("%lld %lld %lld", &x, &k, &y);
    for (int i = 0; i < n; ++i) scanf("%d", a + i);
    for (int i = 0; i < m; ++i) scanf("%d", b + i);
    
    long long res = 0;
    int lst = -1, posa = 0, posb = 0;
    while (posb < m) {
        while(posa < n && a[posa] != b[posb]) ++posa;
        if (posa == n) {
            puts("-1");
            return 0;
        }
        
        if (!upd(lst + 1, posa - 1, res)) {
            puts("-1");
            return 0;
        }
        
        lst = posa;
        ++posb;
    }
    
    if (!upd(lst + 1, n - 1, res)) {
        puts("-1");
        return 0;
    }
    
    printf("%lld\n", res);
    
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int L = 20;

vector<int> g[2 * N];
int p[2 * N];
int up[2 * N][L];
int idx[N];
int psum[N];
int cur[N];
int tin[2 * N];
int tout[2 * N];
int T = 0;

void dfs(int x, int y)
{
	tin[x] = T++;
	p[x] = y;
	up[x][0] = y;
	for(int i = 1; i < L; i++)
		up[x][i] = up[up[x][i - 1]][i - 1];
	for(auto z : g[x])
		dfs(z, x);
	tout[x] = T++;
}

bool is_ancestor(int x, int y)
{
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int lca(int x, int y)
{
	if(is_ancestor(x, y))
		return x;
	for(int i = L - 1; i >= 0; i--)
		if(!is_ancestor(up[x][i], y))
			x = up[x][i];
	return p[x];
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &idx[i]);
		idx[i]--;
	}
	for(int i = 0; i < m; i++)
		cur[i] = i;
	for(int i = 0; i < m - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		int nidx = m + i;
		g[nidx].push_back(cur[x]);
		g[nidx].push_back(cur[y]);
		cur[x] = nidx;
	}
	int root = m * 2 - 2;
	dfs(root, root);
	for(int i = 0; i < n - 1; i++)
	{
		int t = lca(idx[i], idx[i + 1]);
		if(t < m)
			psum[0]++;
		else
			psum[t - m + 1]++;
	}
	for(int i = 0; i < m - 1; i++)
		psum[i + 1] += psum[i];
	for(int i = 0; i < m; i++)
		printf("%d\n", n - 1 - psum[i]);
}

#include <bits/stdc++.h>

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

using namespace std;

int n, m;
vector<int> p;
vector<vector<int>> val;
vector<int> who;

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

int main(){
	scanf("%d%d", &n, &m);
	p.resize(m);
	val.resize(m);
	who.resize(n);
	int ans = n - 1;
	forn(i, m)
		p[i] = i;
	forn(i, n){
		int x;
		scanf("%d", &x);
		--x;
		who[i] = x;
		ans -= (i && who[i] == who[i - 1]);
		val[who[i]].push_back(i);
	}
	printf("%d\n", ans);
	forn(i, m - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		v = getp(v - 1), u = getp(u - 1);
		if (val[v].size() < val[u].size())
			swap(v, u);
		for (int x : val[u]){
			if (x) ans -= who[x - 1] == v;
			if (x < n - 1) ans -= who[x + 1] == v;
		}
		for (int x : val[u]){
			val[v].push_back(x);
			who[x] = v;
		}
		p[u] = v;
		printf("%d\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 998244353;
const int N = 500 * 1000 + 13;

string s;

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

struct node{
	int val[4], len;
};

node merge(const node &a, const node &b, int l, int r){
	node c;
	int na = a.len == 1 ? 0 : 1;
	int nb = b.len == 1 ? 0 : 2;
	c.len = a.len + b.len;
	c.val[0] = mul(a.val[na], b.val[nb]);
	c.val[1] = mul(a.val[na], b.val[3]);
	c.val[2] = mul(a.val[3], b.val[nb]);
	c.val[3] = mul(a.val[3], b.val[3]);
	if (l == 1){
		na = a.len == 1 ? 2 : 0;
		nb = b.len == 1 ? 1 : 0;
		c.val[na + nb] = add(c.val[na + nb], mul(mul(a.val[0], b.val[0]), 19 - (l * 10 + r)));
		c.val[1 + na] = add(c.val[1 + na], mul(mul(a.val[0], b.val[1]), 19 - (l * 10 + r)));
		c.val[2 + nb] = add(c.val[2 + nb], mul(mul(a.val[2], b.val[0]), 19 - (l * 10 + r)));
		c.val[3] = add(c.val[3], mul(mul(a.val[2], b.val[1]), 19 - (l * 10 + r)));
	}
	return c;
}

node t[4 * N];

void build(int v, int l, int r){
	t[v].len = r - l;
	if (l == r - 1){
		t[v].val[0] = 1;
		t[v].val[3] = s[l] + 1;
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}

void upd(int v, int l, int r, int x, int val){
	if (l == r - 1){
		s[l] = val;
		t[v].val[3] = s[l] + 1;
		return;
	}
	int m = (l + r) / 2;
	if (x < m)
		upd(v * 2, l, m, x, val);
	else
		upd(v * 2 + 1, m, r, x, val);
	t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}

int main(){
	int n, m;

	scanf("%d%d", &n, &m);
	static char buf[N];
	scanf("%s", buf);
	s = buf;
	forn(i, n) s[i] -= '0';
	
	memset(t, 0, sizeof(t));
	build(1, 0, n);
	
	forn(i, m){
		int x, v;
		scanf("%d%d", &x, &v);
		--x;
		upd(1, 0, n, x, v);
		printf("%d\n", t[1].val[3]);
	}
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(5e5) + 9;
const int MOD = 998244353;

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

void add(int &a, int x) {
    a += x;
    a %= MOD;
}

int bp(int a, int n) {
    int res = 1;
    for (; n > 0; n >>= 1) {
        if (n & 1) res = mul(res, a);
        a = mul(a, a);
    }
    return res;
}

int inv(int a) {
    int ia = bp(a, MOD - 2);
    assert(mul(a, ia) == 1);
    return ia;
}

int n, m;
string s;
int dp[N][10];
int idp[N][10];
set <pair<int, int> > lr;
int res = 1;

void updRes(int l, int r, int c) {
    assert(l <= r);
    if (c == 1) {
        assert(!lr.count(make_pair(l, r)));
        lr.insert(make_pair(l, r));
        res = mul(res, dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']);
    } else {
        assert(lr.count(make_pair(l, r)));
        lr.erase(make_pair(l, r));
        res = mul(res, inv(dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']));
    }
}

void getLR(int &l, int &r, int pos) {
    l = r = -1;
    auto it = lr.lower_bound(make_pair(pos, n));
    if(it == lr.begin()) return;
    --it;
    if(!(it->first <= pos && pos <= it->second)) return;
    l = it->first, r = it->second;
}

char buf[N];
int main(){
    scanf("%d %d\n", &n, &m);
    scanf("%s", buf);
    s = string(buf);
    for (int i = 0; i <= 9; ++i) {
        dp[0][i] = i + 1; //idp[0][i] = inv(dp[0][i]);
        dp[1][i] = 2 * (i + 1) + (9 - i); //idp[1][i] = inv(dp[1][i]);
    }
    for (int i = 2; i < N; ++i)
        for (int j = 0; j <= 9; ++j) {
            dp[i][j] = (2LL * dp[i - 1][j] + 8LL * dp[i - 2][j]) % MOD;
            //idp[i][j] = inv(dp[i][j]);
        }
    for (int i = 0; i < N; ++i) for(int j = 0; j < 10; ++j) assert(dp[i][j] != 0);
    for (int l = 0; l < n; ) {
        int r = l;
        while(r < n && s[r] == '1') ++r;
        res = mul(res, dp[r - l - (r == n)][r == n? 1 : s[r] - '0']);
        if (l != r) lr.insert(make_pair(l, r - 1));
        l = r + 1;
    }
    
    for (int i = 0; i < m; ++i) {
        int pos;
        char x;
        scanf("%d %c\n", &pos, &x);
        --pos;
        if (x == '1') {
            if (s[pos] != '1'){ 
                int l1, r1, l2, r2;
                getLR(l1, r1, pos - 1);
                getLR(l2, r2, pos + 1);
                
                int l = pos, r = pos;
                if (l1 != -1) {
                    assert(r1 == pos - 1);
                    updRes(l1, r1, -1);
                    l = l1;
                } else {
                    res = mul(res, inv(dp[0][s[pos] - '0']));
                }
                
                if (l2 != -1) {
                    assert(l2 == pos + 1);
                    updRes(l2, r2, -1);
                    r = r2;
                } else {
                    if (pos + 1 != n) res = mul(res, inv(dp[0][s[pos + 1] - '0']));
                }
                
                s[pos] = x;
                updRes(l, r, 1);
            }
        } else {
            if (s[pos] != '1') {
                if (pos - 1 >= 0 && s[pos - 1] == '1') {
                    int l, r;
                    getLR(l, r, pos - 1);
                    updRes(l, r, -1);
                    s[pos] = x;
                    updRes(l, r, 1);
                } else {
                    res = mul(res, dp[0][x - '0']);
                    res = mul(res, inv(dp[0][s[pos] - '0']));
                    s[pos] = x;
                }
            } else {
                int l, r;
                getLR(l, r, pos);
                assert(l != -1 && r != -1);
                
                updRes(l, r, -1);
                s[pos] = x;
                if (l == r) {
                    res = mul(res, dp[0][s[pos] - '0']);
                    if (pos + 1 < n) res = mul(res, dp[0][s[pos + 1] - '0']);
                } else if (pos == l) {
                    res = mul(res, dp[0][s[pos] - '0']);
                    updRes(l + 1, r, 1);
                } else if (pos == r) {
                    if (pos + 1 != n) res = mul(res, dp[0][s[pos + 1] - '0']);
                    updRes(l, r - 1, 1);
                } else {
                    updRes(l, pos - 1, 1);
                    updRes(pos + 1, r, 1);
                }
            }
            
        }
        printf("%d\n", res);
    }
}

At first, let's say that the expected value is equal to the average of total earnings over all positions and is equal to the sum of earnings over all positions divided by $$$n$$$. So we can trasition to minimizing the sum.

Let's learn how to solve the task for some fixed $$$k$$$. Fix some arrangement and rotate the rooms so that the last room contains a mimic. So now you have $$$cnt_1$$$ regular chests, then a single mimic, $$$cnt_2$$$ regular chests, single mimic, $$$\dots$$$, $$$cnt_k$$$ regular chests, single mimic. All $$$cnt_i \ge 0$$$ and $$$\sum \limits_{i=1}^{k} cnt_i = n - k$$$.

Take a look at some of these intervals of length $$$cnt_i$$$. The last chest in the interval is taken from $$$cnt_i$$$ starting positions, the second-to-last is taken $$$cnt_i - 1$$$ times and so on.

Now let's find the optimal way to choose $$$cnt_i$$$. Fix some values of $$$cnt_i$$$. Take a look at the smallest of these values and the largest of them. Let the values be $$$x$$$ and $$$y$$$. If they differ by at least $$$2$$$ ($$$x \le y - 2$$$), then the smaller result can always be achieved by moving a regular chest from the larger one to the smaller one.

Now we have all $$$cnt_i$$$ set now. The only thing left is to assign chests optimally. Write down the union of all the coefficient sequences from all the intervals $$$\bigcup \limits_{i=1}^{n-k} [1, \dots, cnt_i-1, cnt_i]$$$ and sort them in the non-decreasing order. It's easy to show that the chests should be sorted in the non-increasing order (really classical thing, you can try proving that by showing that any other arrangement can easily be improved once again).

That allows us to write a solution in $$$O(n^2)$$$. Sort all the chests in the beginning, after that for some $$$k$$$ multiply the value of the $$$i$$$-th chest by $$$\lfloor \frac{i}{k} \rfloor$$$ and sum up the results.

Finally, let's speed this up with prefix sums. Notice that the first $$$k$$$ values are multiplied by $$$0$$$, the second $$$k$$$ values — by $$$1$$$ and so on. If $$$n$$$ is not divisible by $$$k$$$, then the last block just has length smaller than $$$k$$$. Thus, we can calculate the answer for some $$$k$$$ in $$$O(\frac{n}{k})$$$. And that's equal to $$$O(\sum \limits_{k=1}^{n} \frac{n}{k})$$$ = $$$O(n \log n)$$$.

Overall complexity: $$$O(n \log n)$$$.

#include <bits/stdc++.h>

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

using namespace std;

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

vector<int> pr;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> c(n);
	forn(i, n)
		scanf("%d", &c[i]);
	sort(c.begin(), c.end(), greater<int>());
	pr.push_back(0);
	forn(i, n)
		pr.push_back(add(pr.back(), c[i]));
	
	int invn = binpow(n, MOD - 2);
	for (int k = 1; k <= n; ++k){
		int ans = 0;
		for (int i = 0, j = 0; i < n; i += k, ++j)
			ans = add(ans, mul(j, add(pr[min(n, i + k)], -pr[i])));
		printf("%d ", mul(ans, invn));
	}
	puts("");
	
	return 0;
}

for tc in range(int(input())):
	a, b, c = map(int, input().split())
	print(1 if a < c else -1, end=" ")
	print(b if c < a * b else -1)

for _ in range(int(input())):
    s = input()
    print('DA' if min(s.count('0'), s.count('1')) % 2 == 1 else 'NET')

for _ in range(int(input())):
    s = input()
    cur, mn, res = 0, 0, len(s)
    for i in range(len(s)):
        cur += 1 if s[i] == '+' else -1
        if cur < mn:
            mn = cur
            res += i + 1
        
    print(res)

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<vector<long long>> dp(n + 1, vector<long long>(3));
		for (int i = 0; i < n; ++i) {
			dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + (i & 1 ? 0 : a[i]));
			if (i + 2 <= n) dp[i + 2][1] = max(dp[i + 2][1], max(dp[i][0], dp[i][1]) + (i & 1 ? a[i] : a[i + 1]));
			dp[i + 1][2] = max(dp[i + 1][2], max({dp[i][0], dp[i][1], dp[i][2]}) + (i & 1 ? 0 : a[i]));
		}
		cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n, k;

bool decimalLess(const string& s, const string& t)
{
	if(s.size() != t.size())
		return s.size() < t.size();
	for(int i = 0; i < s.size(); i++)
		if(s[i] != t[i])
			return s[i] < t[i];
	return false;
}

void upd(string& ans, const string& cur)
{
	if(ans == "-1" || decimalLess(cur, ans))
		ans = cur;
}

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

void solve()
{
	string ans = "-1";
	for(int i = 0; i <= 9; i++)
	{
		int cnt9 = n / 9;
		if(i + k < 10)
			cnt9 = 0;
		for(int j = 0; j <= cnt9; j++)
		{
		    if(i + k >= 10 && j == 0)
		        continue;
			int curSum = (i + (i + k)) * (k + 1) / 2;
			if(j != 0)
			{
				int cntBefore = 10 - i;
				int cntAfter = k + 1 - cntBefore;
				curSum = (i + 9) * cntBefore / 2 + cntBefore * 9 * (j - 1) + (1 + cntAfter) * cntAfter / 2;
			}
			curSum = n - curSum;
			if(curSum < 0 || curSum % (k + 1) != 0)
				continue;
			string curNum = {char('0' + i)};
			for(int z = 0; z < j - 1; z++)
				curNum += "9";
			int maxNum = 9;
			if(i + k >= 10)
				maxNum = 8;
			curSum /= (k + 1);
			while(curSum != 0)
			{
				int d = min(curSum, maxNum);
				maxNum = 9;
				curSum -= d;
				curNum.push_back(char('0' + d));
			}
			reverse(curNum.begin(), curNum.end());
			upd(ans, curNum);
		}
	}
	cout << ans << endl;
}

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

def get(s):
	return str(s % 9) + '9' * (s // 9)

for tc in range(int(input())):
	n, k = map(int, input().split())
	k += 1
	bst = 10**100
	for d in range(10):
		ends = 0
		for i in range(k):
			ends += (d + i) % 10
		if ends > n:
			continue
		if d + k > 10:
			for cnt in range(12):
				s = 9 * cnt * (10 - d)
				if s > n - ends:
					break
				for nd in range(9):
					ns = s + (10 - d) * nd + (k - (10 - d)) * (nd + 1)
					if ns > n - ends:
						break
					if (n - ends - ns) % k == 0:
						bst = min(bst, int(get((n - ends - ns) // k) + str(nd) + '9' * cnt + str(d)))
		elif (n - ends) % k == 0:
			bst = min(bst, int(get((n - ends) // k) + str(d)))
	print(-1 if bst == 10**100 else bst)

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

int n;
vector<int> a, b;

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

struct func {
	int minx, mink, maxk;
	func() : minx(0), mink(0), maxk(0) {}
	func(int minx, int mink, int maxk) : minx(minx), mink(mink), maxk(maxk) {}
};

func getFunc(int a, int b) {
	if (a <= b)
		return func(0, b - a, b);
	else
		return func(a - b, 0, b);
}

func merge(func a, func b) {
	if (a.minx == -1 || b.minx == -1)
		return func(-1, -1, -1);
	
	if (a.maxk < b.minx)
		return func(-1, -1, -1);
	if (a.mink >= b.minx)
		return func(a.minx, min(b.maxk, b.mink + (a.mink - b.minx)), min(b.maxk, b.mink + (a.maxk - b.minx)));
	else {
		int add = b.minx - a.mink;
		return func(a.minx + add, b.mink, min(b.maxk, b.mink + (a.maxk - b.minx)));
	}
}

inline void solve() {
	func total = getFunc(a[0], b[0]);
	fore(i, 1, n)
		total = merge(total, getFunc(a[i], b[i]));
	
	if (total.minx != -1 && total.minx <= total.mink)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	
	while(tc--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

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

typedef long long li;
const int N = 1000 * 1000 + 13;

int n;
int a[N], b[N];
 
void solve() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
	for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
	
	li need = 0, add = 0, extra = 2e9;
	for (int i = n - 1; i >= 0; --i) {
		if (b[i] < need) {
			puts("NO");
			return;
		}
		
		li val = b[i] - a[i];
		li to_add = min(extra, max(0LL, val - need));
		add += to_add;
		extra = min(extra - to_add, b[i] - need - to_add);
		need = max(0LL, need - val);
	}
	
	puts(add >= need ? "YES" : "NO");
}
 
int main() {
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; ++i)
		solve();
}

#include <bits/stdc++.h>

using namespace std;

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

int n, k;
int m;
int t[8 * N];
int add[8 * N];
int cnt[2 * N];

void push(int v, int l, int r) {
    if (r - l != 1 && add[v] != 0) {
        t[v * 2 + 1] += add[v];
        t[v * 2 + 2] += add[v];
        add[v * 2 + 1] += add[v];
        add[v * 2 + 2] += add[v];
        add[v] = 0;
    }
}

void upd(int v, int l, int r, int L, int R, int x) {
    if (L >= R) return;
    if(l == L && r == R) {
        t[v] += x;
        add[v] += x;
        return;
    } 
    
    push(v, l, r);
    int mid = (l + r) / 2;
    upd(v * 2 + 1, l, mid, L, min(R, mid), x);
    upd(v * 2 + 2, mid, r, max(L, mid), R, x);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}

void upd(int l, int r, int x) {
    upd(0, 0, n + n, l, r, x);
}

int get(int v, int l, int r, int L, int R) {
    if (L >= R) return 0;
    if (l == L && r == R) return t[v];
    
    push(v, l, r);
    int mid = (l + r) >> 1;
    return max(get(v * 2 + 1, l, mid, L, min(R, mid))
    		 , get(v * 2 + 2, mid, r, max(L, mid), R));
}

int get(int l, int r) {
    return get(0, 0, n + n, l, r);
}

int getAns(set <int> &smx) {
    if (smx.empty()) return 0;
    return max(0, get(0, *smx.rbegin() + 1) - n);
}

void build(int v, int l, int r) {
    if (r - l == 1) {
        t[v] = l;
        return;
    }
    
    int mid = (l + r) >> 1;
    build(v * 2 + 1, l, mid);
    build(v * 2 + 2, mid, r);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}

int main(){
    scanf("%d %d %d", &n, &k, &m);
    
    build(0, 0, n + n);
    set <pair<int, int> > s;
    set <int> smx;
    for (int i = 0; i < m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        int pos = abs(x - k) + y - 1;
        pair <int, int> p = make_pair(x, y);
        if (s.count(p)) {
            --cnt[pos];
            if (cnt[pos] == 0) smx.erase(pos);
            upd(0, pos + 1, -1);
            s.erase(p);
        } else {
            ++cnt[pos];
            if (cnt[pos] == 1) smx.insert(pos);
            upd(0, pos + 1, 1);
            s.insert(p);
        }
        
        printf("%d\n", getAns(smx));
    }
    return 0;
}

for _ in range(int(input())):
    l, r = map(int, input().split())
    print(min(l, r, (l + r) // 3))

for _ in range(int(input())):
    n, x, m = map(int, input().split())
    l, r = x, x
    for _ in range(m):
        L, R = map(int, input().split())
        if max(l, L) <= min(r, R):
            l = min(l, L)
            r = max(r, R)
            
    print(r - l + 1)

#include <bits/stdc++.h>

using namespace std;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int> > a(n, vector<int>(m));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> a[i][j];
	vector<vector<int> > cnt(n + m - 1, vector<int>(2));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cnt[i + j][a[i][j]]++;
	int ans = 0;
	for(int i = 0; i <= n + m - 2; i++)
	{
		int j = n + m - 2 - i;
		if(i <= j) continue;
		ans += min(cnt[i][0] + cnt[j][0], cnt[i][1] + cnt[j][1]);
	}
	cout << ans << endl;
}

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

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

    val minDiv = IntArray(1e7.toInt() + 2) { it }
    for (i in 2 until minDiv.size) {
        if (minDiv[i] != i)
            continue
        for (j in i until minDiv.size step i)
            minDiv[j] = minOf(minDiv[j], i)
    }

    fun getPrimeDivisors(v: Int): ArrayList<Int> {
        val ans = ArrayList<Int>()
        var curVal = v
        while (curVal != 1) {
            if (ans.isEmpty() || ans.last() != minDiv[curVal])
                ans.add(minDiv[curVal])
            curVal /= minDiv[curVal]
        }
        return ans
    }

    val d1 = IntArray(n)
    val d2 = IntArray(n)
    for (id in a.indices) {
        val list = getPrimeDivisors(a[id])
        if (list.size < 2) {
            d1[id] = -1
            d2[id] = -1
        } else {
            d1[id] = list[0]
            list.removeAt(0)
            d2[id] = list.reduce { s, t -> s * t }
        }
    }
    println(d1.joinToString(" "))
    println(d2.joinToString(" "))
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
const int MOD = 998244353;

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

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

int main() {	
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", a + i);
    for (int i = 0; i < m; ++i) scanf("%d", b + i);
    
    reverse(a, a + n);
    reverse(b, b + m);
    a[n] = -1;
    
    int mn = a[0];
    int pos = 0;
    while (pos < n && mn > b[0]) {
        ++pos;
        mn = min(mn, a[pos]);
    }
    
    if (pos == n || mn < b[0]) {
       puts("0");
       return 0;
    }
    
    assert(mn == b[0]);
    int res = 1;
    int ib = 0;
    while (true) {
        assert(mn == b[ib]);
        if (ib == m - 1){
            if(*min_element(a + pos, a + n) != b[ib]) {
               puts("0");
               return 0;
            }
            break;
        }
        
        bool f = true;
        int npos = pos;
        while (npos < n && mn != b[ib + 1]) {
            ++npos;
            mn = min(mn, a[npos]);
            
            if (f && mn < b[ib]){
                f = false;
                res = mul(res, npos - pos);
            }
        }
        
        if (npos == n || mn != b[ib + 1]) {
            puts("0");
            return 0;
        }
        
        ++ib;
        pos = npos;
    }
    
    printf("%d\n", res);
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const long long INF = 1e18;
const int MOD = 1000'000'007;
const int inv2 = (MOD + 1) / 2;

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

struct frac{
	long long x, y;
	frac(long long a, long long b){
		if (b < 0) a = -a, b = -b;
		x = a, y = b;
	}
};

bool operator <=(const frac &a, const frac &b){
	return a.x * b.y <= a.y * b.x;
}

struct line{
	long long m, c;
	frac intersectX(const line &l) { return frac(c - l.c, l.m - m); }
};

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 calc(int a1, int d, int n){
	assert(n >= 0);
	return mul(mul(n, inv2), add(mul(2, a1), mul(add(n, -1), d)));
}

int main() {
	int n, m;
	long long q;
	scanf("%d%d%lld", &n, &m, &q);
	vector<edge> e(m);
	vector<int> hv(n);
	forn(i, m){
		scanf("%d%d%d", &e[i].v, &e[i].u, &e[i].w);
		--e[i].v, --e[i].u;
		hv[e[i].v] = max(hv[e[i].v], e[i].w);
		hv[e[i].u] = max(hv[e[i].u], e[i].w);
	}
	
	int ans = 0;
	vector<long long> d(n, -INF), nd(n);
	d[0] = 0;
	forn(val, m){
		long long mx = 0;
		forn(i, n)
			mx = max(mx, d[i]);
		if (val)
			ans = add(ans, mx % MOD);
		nd = d;
		forn(i, m){
			nd[e[i].v] = max(nd[e[i].v], d[e[i].u] + e[i].w);
			nd[e[i].u] = max(nd[e[i].u], d[e[i].v] + e[i].w);
		}
		d = nd;
	}
	
	vector<line> fin;
	forn(i, n) fin.push_back({hv[i], d[i]});
	sort(fin.begin(), fin.end(), [](const line &a, const line &b){
		if (a.m != b.m)
			return a.m < b.m;
		return a.c > b.c;
	});
	fin.resize(unique(fin.begin(), fin.end(), [](const line &a, const line &b){
		return a.m == b.m;
	}) - fin.begin());
	
	vector<line> ch;
	for (auto cur : fin){
		while (ch.size() >= 2 && cur.intersectX(ch.back()) <= ch.back().intersectX(ch[int(ch.size()) - 2]))
			ch.pop_back();
		ch.push_back(cur);
	}
	
	long long prv = 0;
	q -= m;
	forn(i, int(ch.size()) - 1){
		frac f = ch[i].intersectX(ch[i + 1]);
		if (f.x < 0) continue;
		long long lst = min(q, f.x / f.y);
		if (lst < prv) continue;
		ans = add(ans, calc((ch[i].c + ch[i].m * prv) % MOD, ch[i].m % MOD, lst - prv + 1));
		prv = lst + 1;
	}
	ans = add(ans, calc((ch.back().c + ch.back().m * prv) % MOD, ch.back().m % MOD, q - prv + 1));
	
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define 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)

const int INF = 1e9;
const int N = 10010;

int n, m;
string s, t;
int dp[N][N];
int nxt[N];

int main() {
	cin >> s >> t;
	n = sz(s), m = sz(t);
	
	forn(i, n) if (s[i] != '.') {
		int bal = 0;
		nxt[i] = -1;
		fore(j, i, n) {
			if (s[j] == '.') --bal;
			else ++bal;
			if (bal == 0) {
				nxt[i] = j;
				break;
			}
		}
	}
	
	forn(i, n + 1) forn(j, m + 1)
		dp[i][j] = INF;
	dp[0][0] = 0;
	
	forn(i, n) forn(j, m + 1) {
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
		if (j < m && s[i] == t[j])
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
		if (s[i] != '.' && nxt[i] != -1)
			dp[nxt[i] + 1][j] = min(dp[nxt[i] + 1][j], dp[i][j]);
	}
	
	cout << dp[n][m] << endl;
}

t = int(input())

for i in range(t):
    n, m, k = map(int, input().split())
    d = n // k
    a1 = min(m, d)
    a2 = (m - a1 + k - 2) // (k - 1)
    print(a1 - a2)

t = int(input())

for i in range(t):
    n, m, k = map(int, input().split())
    ans = 0
    d = n // k
    for a1 in range(m + 1):
        for a2 in range(a1 + 1):
            if(a1 > d):
                continue
            if(a1 + a2 > m):
                continue
            if(a1 + (k - 1) * a2 < m):
                continue
            ans = max(ans, a1 - a2)
    print(ans)

t = int(input())
for _ in range(t):
	n, m, x, y = map(int, input().split())
	ans = 0
	y = min(y, 2 * x)
	for __ in range(n):
		s = input()
		i = 0
		while i < m:
			if s[i] == '*':
				i += 1
				continue
			j = i
			while j + 1 < m and s[j + 1] == '.':
				j += 1
			l = j - i + 1
			ans += l % 2 * x + l // 2 * y
			i = j + 1
	print(ans)

So there are two kinds of stops to consider: $$$k$$$ hot and $$$k$$$ cold cup and $$$(k + 1)$$$ hot and $$$k$$$ cold cups.

The first case is trivial: the temperature is always $$$\frac{h + c}{2}$$$. In the second case the temperature is always strictly greater than $$$\frac{h + c}{2}$$$. Thus, if $$$t \le \frac{h + c}{2}$$$, then the answer is $$$2$$$.

Let's show that otherwise the answer is always achieved through the second case.

The temperature after $$$(k + 1)$$$ hot cups and $$$k$$$ cold cups is $$$t_k = \frac{(k + 1) \cdot h + k \cdot c}{2k + 1}$$$. The claim is that $$$t_0 > t_1 > \dots$$$. Let's prove that by induction.

We can also show that this series converges to $$$\frac{h + c}{2}$$$:

So that claim makes us see that for any $$$t$$$ greater than $$$\frac{h + c}{2}$$$ the answer is always achieved from the second case.

That allows us to find such $$$k$$$, that the value of $$$t_k$$$ is exactly $$$t$$$. However, such $$$k$$$ might not be integer. $$$\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} = t \leftrightarrow$$$ $$$\frac{k \cdot (h + c) + h}{2k + 1} = t \leftrightarrow$$$ $$$k \cdot (h + c) + h = 2kt + t \leftrightarrow$$$ $$$k \cdot (h + c - 2t) = t - h \leftrightarrow$$$ $$$k = \frac{t - h}{h + c - 2t}$$$.

The only thing left is to compare which side is better to round $$$k$$$ to. It seems some implementations with float numbers might fail due to precision errors. However, it's possible to do these calculations completely in integers.

Let's actually rewrite that so that the denominator is always positive $$$k = \frac{h - t}{2t - h - c}$$$. Now we can round this value down and compare $$$k$$$ and $$$k + 1$$$.

So the optimal value is $$$k$$$ if $$$|\frac{k \cdot (h + c) + h}{2k + 1} - t| \le |\frac{(k + 1) \cdot (h + c) + h}{2k + 3} - t|$$$. So $$$|(k \cdot (h + c) + h) - t \cdot (2k + 1)| \cdot (2k + 3) \le |((k + 1) \cdot (h + c) + h) - t \cdot (2k + 3)| \cdot (2k + 1)$$$. Otherwise, the answer is $$$k + 1$$$.

You can also find the optimal $$$k$$$ with binary search but the formulas are exactly the same and you have to rely on monotonosity as well. Also, these formulas can get you the better understanding for the upper bound of the answer.

Overall complexity: $$$O(1)$$$ or $$$O(\log h)$$$ per testcase.

#include <bits/stdc++.h>

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

using namespace std;


int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		int h, c, t;
		scanf("%d%d%d", &h, &c, &t);
		if (h + c - 2 * t >= 0)
			puts("2");
		else{
			int a = h - t;
			int b = 2 * t - c - h;
			int k = 2 * (a / b) + 1;
			long long val1 = abs(k / 2 * 1ll * c + (k + 1) / 2 * 1ll * h - t * 1ll * k);
			long long val2 = abs((k + 2) / 2 * 1ll * c + (k + 3) / 2 * 1ll * h - t * 1ll * (k + 2));
			printf("%d\n", val1 * (k + 2) <= val2 * k ? k : k + 2);
		}
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	long long ans = 0;
	forn(mx, 31){
		long long cur = 0;
		long long best = 0;
		forn(i, n){
			int val = (a[i] > mx ? -INF : a[i]);
			cur += val;
			best = min(best, cur);
			ans = max(ans, (cur - best) - mx);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 500043;
const int MOD = 998244353;

int fact[N];

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

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

int binpow(int x, int y)
{
	int z = 1;
	while(y > 0)
	{
		if(y % 2 == 1)
			z = mul(z, x);
		x = mul(x, x);
		y /= 2;
	}
	return z;
}

int inv(int x)
{
	return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
	return mul(x, inv(y));
}

void precalc()
{
	fact[0] = 1;
	for(int i = 1; i < N; i++)
		fact[i] = mul(i, fact[i - 1]);
}

int C(int n, int k)
{
	if(k > n) return 0;
	return divide(fact[n], mul(fact[n - k], fact[k]));
}

int main()
{
	int n, k;
	cin >> n >> k;
	int ans = 0;
	precalc();
	for(int i = 1; i <= n; i++)
	{
		int d = n / i;
		ans = add(ans, C(d - 1, k - 1));
	}
	cout << ans << 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;

const double INF = 1e13;

struct line{
	int A, B, C;
	line(){}
	line(int x1, int y1, int x2, int y2){
		A = y1 - y2;
		B = x2 - x1;
		C = -A * x1 - B * y1;
		// A is guaranteed to be non-zero
		if (A < 0) A = -A, B = -B, C = -C;
		int g = __gcd(A, __gcd(abs(B), abs(C)));
		A /= g, B /= g, C /= g;
	}
};

bool operator ==(const line &a, const line &b){
	return a.A == b.A && a.B == b.B && a.C == b.C;
}

double x;

bool operator <(const line &a, const line &b){
	double val1 = (-a.A * x - a.C) / a.B;
	double val2 = (-b.A * x - b.C) / b.B;
	return val1 < val2;
}

struct car{
	int x, y, dx, dy, s;
	line l;
	double vx, vy;
};

int n;
vector<car> a(n);

long long det(int a, int b, int c, int d){
	return a * 1ll * d - b * 1ll * c;
}

bool inter(const line &a, const line &b, long long &D, long long &Dx, long long &Dy){
	D = det(a.A, a.B, b.A, b.B);
	if (D == 0) return false;
	Dx = -det(a.C, a.B, b.C, b.B);
	Dy = -det(a.A, a.C, b.A, b.C);
	return true;
}

int sg(int x){
	return x < 0 ? -1 : 1;
}

int sg(long long a, long long b, int c){
	// sign of a/b-c
	if (b < 0) a = -a, b = -b;
	return a - c * b < 0 ? -1 : (a - c * b > 0);
}

bool inter(int i, int j, double &len){
	if (i == -1 || j == -1)
		return false;
	long long D, Dx, Dy;
	if (!inter(a[i].l, a[j].l, D, Dx, Dy))
		return false;
	if (sg(Dx, D, a[i].x) != 0 && sg(a[i].dx) != sg(Dx, D, a[i].x))
		return false;
	if (sg(Dx, D, a[j].x) != 0 && sg(a[j].dx) != sg(Dx, D, a[j].x))
		return false;
	double x = Dx / double(D);
	double y = Dy / double(D);
	double di = (a[i].x - x) * (a[i].x - x) + (a[i].y - y) * (a[i].y - y);
	double dj = (a[j].x - x) * (a[j].x - x) + (a[j].y - y) * (a[j].y - y);
	return len * len >= di / a[i].s && len * len >= dj / a[j].s;
}

vector<set<pair<line, int>>::iterator> del;
set<pair<line, int>> q;

void get_neighbours(int i, int &l, int &r){
	l = r = -1;
	auto it = q.lower_bound({a[i].l, -1});
	if (it != q.end())
		r = it->y;
	if (!q.empty() && it != q.begin()){
		--it;
		l = it->y;
	}
}

bool check(double t){
	vector<pair<double, pair<int, int>>> cur;
	del.resize(n);
	forn(i, n){
		double x1 = a[i].x;
		double x2 = a[i].x + a[i].vx * t;
		if (x1 > x2) swap(x1, x2);
		cur.push_back({x1, {i, 0}});
		cur.push_back({x2, {i, 1}});
	}
	q.clear();
	
	sort(cur.begin(), cur.end());
	for (auto &qr : cur){		
		x = qr.x;
		int i = qr.y.x;
		int l, r;
		
		if (qr.y.y == 0){
			get_neighbours(i, l, r);
			
			if (r != -1 && a[i].l == a[r].l)
				return true;
			if (inter(i, l, t))
				return true;
			if (inter(i, r, t))
				return true;
			
			del[i] = q.insert({a[i].l, i}).x;
		}
		else{			
			q.erase(del[i]);
			get_neighbours(i, l, r);
			
			if (inter(l, r, t))
				return true;
		}
	}
	return false;
}

int main() {
	scanf("%d", &n);
	a.resize(n);
	forn(i, n){
		scanf("%d%d%d%d%d", &a[i].x, &a[i].y, &a[i].dx, &a[i].dy, &a[i].s);
		a[i].l = line(a[i].x, a[i].y, a[i].x + a[i].dx, a[i].y + a[i].dy);
		double d = sqrt(a[i].dx * a[i].dx + a[i].dy * a[i].dy);
		a[i].vx = a[i].dx / d * a[i].s;
		a[i].vy = a[i].dy / d * a[i].s;
		a[i].s *= a[i].s;
	}
	double l = 0, r = INF;
	bool ok = false;
	forn(_, 100){
		double m = (l + r) / 2;
		if (check(m)){
			ok = true;
			r = m;
		}
		else{
			l = m;
		}
	}
	if (!ok)
		puts("No show :(");
	else
		printf("%.15lf\n", l);
	return 0;
}

t = int(input())
for _ in range(t):
	a, b, c, d = map(int, input().split())
	if b >= a:
		print(b)
		continue
	if c <= d:
		print(-1)
		continue
	a -= b
	dif = c - d
	print(b + (a + dif - 1) // dif * c)

#include<bits/stdc++.h>

using namespace std;

char buf[200043];

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++)
	{
		scanf("%s", buf);
		string s = buf;
		int ans = int(1e9);
		int n = s.size();
		vector<pair<char, int> > c;
		for(auto x : s)
		{
			if(c.empty() || c.back().first != x)
				c.push_back(make_pair(x, 1));
			else
				c.back().second++;
		}
		int m = c.size();
		for(int i = 1; i < m - 1; i++)
			if(c[i - 1].first != c[i + 1].first)
				ans = min(ans, c[i].second + 2);
		if(ans > n)
			ans = 0;
		printf("%d\n", ans);
	}
}

import kotlin.math.*

fun main() {
    val PI = acos(-1.0)
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val n = readLine()!!.toInt()
        var ans : Double
        if (n % 2 == 0) {
            ans = 1.0 / tan(PI / (2 * n))
        } else {
            ans = cos(PI / (4 * n)) / sin(PI / (2 * n))
        }
        println("%.9f".format(ans))
    }
}

#include<bits/stdc++.h>

using namespace std;

int n, q;
vector<int> a, k;

int count_le(int x)
{
	int cnt = 0;
	for(auto y : a)
		if(y <= x)
			cnt++;
	for(auto y : k)
	{
		if(y > 0 && y <= x)
			cnt++;
		if(y < 0 && abs(y) <= cnt)
			cnt--;
	}
	return cnt;
}

int main()
{
	scanf("%d %d", &n, &q);
	a.resize(n);
	k.resize(q);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for(int i = 0; i < q; i++)
		scanf("%d", &k[i]);
	if(count_le(int(1e9)) == 0)
	{
		puts("0");
		return 0;
	}
	int lf = 0;
	int rg = int(1e6) + 1;
	while(rg - lf > 1)
	{
		int mid = (lf + rg) / 2;
		if(count_le(mid) > 0)
			rg = mid;
		else
			lf = mid;
	}
	printf("%d\n", rg);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

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

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 5000 + 7;

int n, m;
int a[3];
vector<int> g[N];

bool read () {
	if (scanf("%d%d", &n, &m) != 2)
		return false;
	forn(i, 3) scanf("%d", &a[i]);
	forn(i, n)
		g[i].clear();
	forn(i, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].pb(u);
		g[u].pb(v);
	}
	return true;
}

int tot0, tot1;
int clr[N];
vector<vector<int>> vts[2];
bool ok;

void dfs(int v){
	tot0 += clr[v] == 0;
	tot1 += clr[v] == 1;
	vts[clr[v]].back().pb(v);
	for (auto u : g[v]){
		if (clr[u] == -1){
			clr[u] = clr[v] ^ 1;
			dfs(u);
		}
		else if (clr[u] == clr[v]){
			ok = false;
		}
	}
}

int dp[N][N];
int res[N];

void solve() {
	vector<pt> siz;
	memset(clr, -1, sizeof(clr));
	vts[0].clear();
	vts[1].clear();
	forn(i, n) if (clr[i] == -1){
		tot0 = tot1 = 0;
		clr[i] = 0;
		ok = true;
		vts[0].pb(vector<int>());
		vts[1].pb(vector<int>());
		dfs(i);
		if (!ok){
			puts("NO");
			return;
		}
		siz.pb(mp(tot0, tot1));
	}
	
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	forn(i, sz(siz)) forn(j, N) if (dp[i][j] != -1){
		dp[i + 1][j + siz[i].x] = 0;
		dp[i + 1][j + siz[i].y] = 1;
	}
	
	if (dp[sz(siz)][a[1]] == -1){
		puts("NO");
		return;
	}
	
	puts("YES");
	memset(res, -1, sizeof(res));
	int cur = a[1];
	for (int i = sz(siz); i > 0; --i){
		for (auto it : vts[dp[i][cur]][i - 1])
			res[it] = 2;
		cur -= sz(vts[dp[i][cur]][i - 1]);
	}
	
	forn(i, n) if (res[i] == -1){
		if (a[0] > 0){
			res[i] = 1;
			--a[0];
		}
		else{
			res[i] = 3;
			--a[2];
		}
	}
	
	forn(i, n) printf("%d", res[i]);
	puts("");
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int tt = clock();
	
#endif
	
	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;

	while(read()) {	
		solve();
		
#ifdef _DEBUG
	cerr << "TIME = " << clock() - tt << endl;
	tt = clock();
#endif

	}
}

#include<bits/stdc++.h>

using namespace std;

const int N = 243;

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

int s, t, V;
vector<int> g[N];
vector<edge> e;

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

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

int p[N];
int d[N];
int pe[N];
int inq[N];

bool enlarge()
{
    for(int i = 0; i < V; i++)
    {
        d[i] = int(1e9);
        p[i] = -1;
        pe[i] = -1;
        inq[i] = 0;
    }
    d[s] = 0;
    queue<int> q;
    q.push(s);
    inq[s] = 1;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        inq[k] = 0;
        for(auto z : g[k])
        {
            if(!rem(z)) continue;
            if(d[e[z].y] > d[k] + e[z].cost)
            {
                p[e[z].y] = k;
                pe[e[z].y] = z;
                d[e[z].y] = d[k] + e[z].cost;
                if(!inq[e[z].y])
                {
                    q.push(e[z].y);
                    inq[e[z].y] = 1;
                }
            }
        }
    }
    if(p[t] == -1)
        return false;
    int cur = t;
    while(cur != s)
    {
        e[pe[cur]].f++;
        e[pe[cur] ^ 1].f--;
        cur = p[cur];
    }
    return true;
}

void process_test()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n), b(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
	}
	s = 2 * n;
	t = 2 * n + 1;
	V = 2 * n + 2;
	for(int i = 0; i < n; i++)
	{
		add(s, i, 1, 0);
		add(i + n, t, 1, 0);
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
		{
			if(j < k - 1)
				add(i, j + n, 1, -(a[i] + b[i] * j));
			else if(j == n - 1)
				add(i, j + n, 1, -(a[i] + b[i] * (k - 1)));
			else
				add(i, j + n, 1, -(b[i] * (k - 1)));
		}
	for(int i = 0; i < n; i++)
		enlarge();
	vector<int> order(n);
	for(int i = 0; i < n; i++)
		for(auto x : g[i])
		{
			int to = e[x].y;
			if(to >= n && to < 2 * n && e[x].f == 1)
				order[to - n] = i;
		}
	cout << k + (n - k) * 2 << endl;
	for(int i = 0; i < n; i++)
	{
		cout << order[i] + 1 << " ";
		if(i >= k - 1 && i < n - 1)
			cout << -(order[i] + 1) << " ";
	}
	cout << endl;
	e.clear();
	for(int i = 0; i < V; i++)
		g[i].clear();
}

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

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void output_vector(const vector<T> &v, bool add_one = false, int start = -1, int end = -1) {
    if (start < 0) start = 0;
    if (end < 0) end = int(v.size());

    for (int i = start; i < end; i++)
        cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
}

const int64_t INF64 = int64_t(2e18) + 5;

vector<int> assignment;

template<typename T>
int64_t hungarian(vector<vector<T>> costs) {
    int n = int(costs.size());
    int m = costs.empty() ? 0 : int(costs[0].size());

    if (n > m) {
        vector<vector<T>> new_costs(m, vector<T>(n));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                new_costs[j][i] = costs[i][j];

        swap(costs, new_costs);
        swap(n, m);
    }

    vector<int64_t> u(n + 1), v(m + 1);
    vector<int> p(m + 1), way(m + 1);

    for (int i = 1; i <= n; i++) {
        vector<int64_t> min_v(m + 1, INF64);
        vector<bool> used(m + 1, false);
        p[0] = i;
        int j0 = 0;

        do {
            used[j0] = true;
            int i0 = p[j0], j1 = 0;
            int64_t delta = INF64;

            for (int j = 1; j <= m; j++)
                if (!used[j]) {
                    int64_t cur = costs[i0 - 1][j - 1] - u[i0] - v[j];

                    if (cur < min_v[j]) {
                        min_v[j] = cur;
                        way[j] = j0;
                    }

                    if (min_v[j] < delta) {
                        delta = min_v[j];
                        j1 = j;
                    }
                }

            for (int j = 0; j <= m; j++)
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    min_v[j] -= delta;
                }

            j0 = j1;
        } while (p[j0] != 0);

        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0 != 0);
    }

    // Note that p[j] is the row assignment of column j (both 1-based). If p[j] = 0, the column is unassigned.
    assignment = p;
    return -v[0];
}


void run_case() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N), B(N);

    for (int i = 0; i < N; i++)
        cin >> A[i] >> B[i];

    vector<vector<int>> costs(N, vector<int>(N, 0));

    for (int i = 0; i < N; i++)
        for (int position = 0; position < N; position++)
            if (position < K)
                costs[i][position] = -(A[i] + position * B[i]);
            else
                costs[i][position] = -((K - 1) * B[i]);

    int64_t score = -hungarian(costs);
    dbg(score);
    vector<int> solution;

    for (int k = 1; k < K; k++)
        solution.push_back(assignment[k]);

    for (int k = K + 1; k <= N; k++) {
        solution.push_back(assignment[k]);
        solution.push_back(-assignment[k]);
    }

    solution.push_back(assignment[K]);
    assert(int(solution.size()) == 2 * N - K);
    cout << solution.size() << '\n';
    output_vector(solution);
}

int main() {
    ios::sync_with_stdio(false);
#ifndef NEAL_DEBUG
    cin.tie(nullptr);
#endif

    int tests;
    cin >> tests;

    while (tests-- > 0)
        run_case();
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++) 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}
 
template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}
 
mt19937 rnd(time(NULL));
 
const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
 
const int N = 100;
 
int n, k;
pair<pt, int> a[N];
 
bool read () {
	if (scanf("%d%d", &n, &k) != 2)
		return false;
	forn(i, n){
		scanf("%d%d", &a[i].x.x, &a[i].x.y);
		a[i].y = i;
	}
	return true;
}
 
int dp[N][N];
int p[N][N];
 
void solve() {
	sort(a, a + n, [](const pair<pt, int> &a, const pair<pt, int> &b){
		if (a.x.y != b.x.y)
			return a.x.y < b.x.y;
		return a.x.x < b.x.x;
	});
	
	forn(i, N) forn(j, N)
		dp[i][j] = -INF;
	dp[0][0] = 0;
	forn(i, n) forn(j, N) if (dp[i][j] >= 0){
		if (dp[i + 1][j] < dp[i][j] + a[i].x.y * (k - 1)){
			dp[i + 1][j] = dp[i][j] + a[i].x.y * (k - 1);
			p[i + 1][j] = j;
		}
		if (dp[i + 1][j + 1] < dp[i][j] + a[i].x.y * j + a[i].x.x){
			dp[i + 1][j + 1] = dp[i][j] + a[i].x.y * j + a[i].x.x;
			p[i + 1][j + 1] = j;
		}
	}
	
	vector<int> ans1, ans2;
	int cur = k;
	for (int i = n; i > 0; --i){
		if (p[i][cur] == cur)
			ans2.pb(a[i - 1].y + 1);
		else
			ans1.pb(a[i - 1].y + 1);
		cur = p[i][cur];
	}
	
	reverse(all(ans1));
	reverse(all(ans2));
	printf("%d\n", sz(ans1) + sz(ans2) * 2);
	forn(i, sz(ans1) - 1)
		printf("%d ", ans1[i]);
	for (auto it : ans2)
		printf("%d %d ", it, -it);
	printf("%d\n", ans1.back());
}
 
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int tt = clock();
	
#endif
	
	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;
 
	int tc;
	scanf("%d", &tc);
	while(tc--) {	
		read();
		solve();
		
#ifdef _DEBUG
	cerr << "TIME = " << clock() - tt << endl;
	tt = clock();
#endif
 
	}
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

const int MAG = 30;
int lst;

int n, k;

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	return true;
}

int ask(int l1, int r1, int l2, int r2) {
	assert(l1 < r1 && l2 < r2);
	assert(r1 <= l2 || r2 <= l1);
	
	cout << "? " << r1 - l1 << " " << r2 - l2 << endl;
	fore(i, l1, r1) {
		if (i > l1) cout << " ";
		cout << i + 1;
	}
	cout << endl;
	fore(i, l2, r2) {
		if (i > l2) cout << " ";
		cout << i + 1;
	}
	cout << endl;
	cout.flush();
	
	string resp;
	cin >> resp;
	
	if (resp == "FIRST")
		return -1;
	if (resp == "SECOND")
		return 1;
	if (resp == "EQUAL")
		return 0;
	
	exit(0);
}

inline void solve() {
	//check first position
	mt19937 rnd(lst ^ (n * 1024 + k));
	for(int q = 0; q < MAG; q++) {
		int cur = 1 + rnd() % (n - 1);
		
		int resp = ask(0, 1, cur, cur + 1);
		if (resp == 1) {
			cout << "! 1" << endl;
			cout.flush();
			return;
		}
	}
	
	int len = 1;
	while(true) {
		int cnt = min(len, n - len);
		int resp = ask(0, cnt, len, len + cnt);
		if (resp != 0) {
			assert(resp == -1);
			break;
		}
		len <<= 1;
	}
	
	int lf = len, rg = min(2 * len, n);
	while(rg - lf > 1) {
		int mid = (lf + rg) >> 1;
		int resp = ask(0, mid - lf, lf, mid);
		assert(resp != 1);
		
		if (resp == 0)
			lf = mid;
		else
			rg = mid;
	}
	cout << "! " << lf + 1 << endl;
	cout.flush();
	
	lst = lf + 1;
}

int main() {
	int tc;
	cin >> tc;
	
	lst = tc;
	while(tc--) {
		assert(read());
		solve();
	}
	return 0;
}

for _ in range(int(input())):
    x, y = map(int, input().split())
    a, b = map(int, input().split())
    b = min(b, a + a)
    if x < y:
        x, y= y, x
    print(y * b + (x - y) * a)

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val t = readLine()!!

        val s = t.toCharArray().distinct().joinToString("").repeat(t.length)
        println(s)
    }
}

#include<bits/stdc++.h>

using namespace std;

const int N = 40043;

int len;
int p[N];

void build(int a, int b)
{
	len = a * b;
	p[0] = 0;
	for(int i = 1; i <= len; i++)
	{
		p[i] = p[i - 1];
		if((i % a) % b != (i % b) % a)
			p[i]++;
	}
}

long long query(long long l)
{
	long long cnt = l / len;
	int rem = l % len;
	return p[len] * 1ll * cnt + p[rem]; 
}

long long query(long long l, long long r)
{
	return query(r) - query(l - 1);
}

int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		int a, b, q;
		cin >> a >> b >> q;
		build(a, b);
		long long l, r;
		for(int j = 0; j < q; j++)
		{
			cin >> l >> r;
			cout << query(l, r) << " ";
		}
		cout << endl;
	}
}

#include <bits/stdc++.h>

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

using namespace std;


int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	vector<int> c(k + 1);
	forn(i, k) scanf("%d", &c[i + 1]);
	
	sort(a.begin(), a.end(), greater<int>());
	int ans = 0;
	for (int i = k, g = 0; i >= 1; --i){
		while (g < n && a[g] == i) ++g;
		ans = max(ans, (g + c[i] - 1) / c[i]);
	}
	vector<vector<int>> res(ans);
	forn(i, n) res[i % ans].push_back(a[i]);
	
	printf("%d\n", ans);
	forn(i, ans){
		printf("%d", int(res[i].size()));
		for (auto it : res[i])
			printf(" %d", it);
		puts("");
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 200043;

int add(int x, int y)
{
	return (x + y) % MOD;
}

int sub(int x, int y)
{
	return add(x, MOD - y);
}

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

int binpow(int x, int y)
{
	int z = 1;
	while(y > 0)
	{
		if(y % 2 == 1)
			z = mul(z, x);
		x = mul(x, x);
		y /= 2;
	}
	return z;
}

int inv(int x)
{
	return binpow(x, MOD - 2);
}

int fact[N];

int C(int n, int k)
{
	return mul(fact[n], inv(mul(fact[k], fact[n - k])));
}

int main()
{
	int n, k;
	cin >> n >> k;
	
	if(k > n - 1)
	{
		cout << 0 << endl;
		return 0;
	}
	
	fact[0] = 1;
	for(int i = 1; i <= n; i++)
		fact[i] = mul(i, fact[i - 1]);
	int ans = 0;
	int c = n - k;
	for(int i = c; i >= 0; i--)
		if(i % 2 == c % 2)
			ans = add(ans, mul(binpow(i, n), C(c, i)));
		else
			ans = sub(ans, mul(binpow(i, n), C(c, i)));
	ans = mul(ans, C(n, c));
	if(k > 0)
		ans = mul(ans, 2);
	cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

const int INF = 1e9;
const int N = 15;

int n;
int a[N];
int sum[1 << N];
int dp[N + 1][1 << N][N + 1];
pt p[N + 1][1 << N][N + 1];

void solve() {
	scanf("%d", &n);
	forn(i, n) scanf("%d", &a[i]);
	
	forn(mask, 1 << n) {
		sum[mask] = 0;
		forn(i, n) if (mask & (1 << i))
			sum[mask] += a[i];
	}	
	
	forn(cnt, n + 1) forn(mask, 1 << n) forn(pos, n + 1)
		dp[cnt][mask][pos] = INF;
	
	dp[0][0][0] = 0;
	forn(cnt, n) forn(mask, 1 << n) forn(pos, n) if (dp[cnt][mask][pos] < INF) {
		int rmask = mask ^ ((1 << n) - 1);
		for (int nmask = rmask; nmask; nmask = (nmask - 1) & rmask) {
			if (sum[nmask] <= dp[cnt][mask][pos])
				continue;
			if ((nmask >> pos) == 0)
				continue;
			int npos = pos + __builtin_ctz(nmask >> pos) + 1;
			if (dp[cnt + 1][mask | nmask][npos] > sum[nmask]) {
				dp[cnt + 1][mask | nmask][npos] = sum[nmask];
				p[cnt + 1][mask | nmask][npos] = mp(mask, pos);
			}
		}
	}
	
	int acnt = 0, apos = 0;
	forn(cnt, n + 1) forn(pos, n + 1) if (dp[cnt][(1 << n) - 1][pos] < INF)
		acnt = cnt, apos = pos;
		
	vector<pt> ans;
	
	int mask = (1 << n) - 1, pos = apos;
	for (int cnt = acnt; cnt > 0; --cnt) {
		int nmask = p[cnt][mask][pos].x;
		int npos = p[cnt][mask][pos].y;
		forn(i, n) if ((nmask ^ mask) & (1 << i))
			if (i != pos - 1) ans.pb(mp(i, pos - 1));
		mask = nmask, pos = npos;
	}
	
	
	printf("%d\n", sz(ans));
	forn(i, sz(ans)) {
		int from = ans[i].x;
		forn(j, i) from -= ans[j].x < ans[i].x;
		int to = ans[i].y;
		forn(j, i) to -= ans[j].x < ans[i].y;
		printf("%d %d\n", from + 1, to + 1);
	}
}	

int main() {
	int tc;
	scanf("%d", &tc);
	forn(i, tc) solve();
		
}

#include <bits/stdc++.h>

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

using namespace std;


int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--){
		int n;
		scanf("%d", &n);
		int p = 0, c = 0;
		bool fl = true;
		forn(i, n){
			int x, y;
			scanf("%d%d", &x, &y);
			if (x < p || y < c || y - c > x - p)
				fl = false;
			p = x, c = y;
		}
		puts(fl ? "YES" : "NO");
	}
	return 0;
}

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val (n, x) = readLine()!!.split(' ').map { it.toInt() }
        val a = readLine()!!.split(' ').map { it.toInt() }.sortedDescending()

        var cnt = 0
        var sum = 0L
        while (cnt < n && sum + a[cnt] >= (cnt + 1) * x.toLong()) {
            sum += a[cnt]
            cnt++
        }
        println(cnt)
    }
}

#include <bits/stdc++.h>

using namespace std;

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

typedef long long li;

const int N = 300 * 1000 + 13;

int n;
li a[N], b[N];

void solve() {
	scanf("%d", &n);
	forn(i, n) scanf("%lld%lld", &a[i], &b[i]);
	
	li ans = 0, mn = 1e18;
	forn(i, n) {
		int ni = (i + 1) % n;
		li val = min(a[ni], b[i]);
		ans += a[ni] - val;
		mn = min(mn, val);
	}
	ans += mn;
	printf("%lld\n", ans);
}

int main() {
	int T;
	scanf("%d", &T);
	forn(i, T)
		solve();
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

int n;
li l, r;

inline bool read() {
	if(!(cin >> n >> l >> r))
		return false;
	return true;
}

bool intersect(li l1, li r1, li l2, li r2) {
	return min(r1, r2) > max(l1, l2);
}

vector<int> ans;

void calc(int lf, int rg, li &id) {
	if(lf == rg) return;
	
	if(intersect(l, r, id, id + 2 * (rg - lf))) {
		fore(to, lf + 1, rg + 1) {
			if(l <= id && id < r)
				ans.push_back(lf);
			id++;
			
			if(l <= id && id < r)
				ans.push_back(to);
			id++;
		}
	} else
		id += 2 * (rg - lf);
	
	calc(lf + 1, rg, id);
	
	if(lf == 0) {
		if(l <= id && id < r)
			ans.push_back(lf);
		id++;
	}
}

inline void solve() {
	ans.clear();
	li id = 0;
	l--;
	calc(0, n - 1, id);
	
	assert(sz(ans) == r - l);
	assert(id == n * li(n - 1) + 1);
	
	for(int v : ans)
		cout << v + 1 << " ";
	cout << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	
	while(tc--) {
		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 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() {
	long long d;
	scanf("%lld", &d);
	int q;
	scanf("%d", &q);
	
	vector<long long> primes;
	for (long long i = 2; i * i <= d; ++i) if (d % i == 0){
		primes.push_back(i);
		while (d % i == 0) d /= i;
	}
	if (d > 1){
		primes.push_back(d);
	}
	
	vector<int> fact(100), rfact(100);
	fact[0] = 1;
	for (int i = 1; i < 100; ++i)
		fact[i] = mul(fact[i - 1], i);
	rfact[99] = binpow(fact[99], MOD - 2);
	for (int i = 98; i >= 0; --i)
		rfact[i] = mul(rfact[i + 1], i + 1);
	
	forn(i, q){
		long long x, y;
		scanf("%lld%lld", &x, &y);
		vector<int> up, dw;
		for (auto p : primes){
			int cnt = 0;
			while (x % p == 0){
				--cnt;
				x /= p;
			}
			while (y % p == 0){
				++cnt;
				y /= p;
			}
			if (cnt < 0) dw.push_back(-cnt);
			else if (cnt > 0) up.push_back(cnt);
		}
		int ans = 1;
		ans = mul(ans, fact[accumulate(up.begin(), up.end(), 0)]);
		for (auto it : up) ans = mul(ans, rfact[it]);
		ans = mul(ans, fact[accumulate(dw.begin(), dw.end(), 0)]);
		for (auto it : dw) ans = mul(ans, rfact[it]);
		printf("%d\n", ans);
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long li;
const li INF64 = li(1e18);
const int N = 500043;

li f[N];

li get(int x)
{
    li ans = 0;    
    for (; x >= 0; x = (x & (x + 1)) - 1)
        ans += f[x];
    return ans;
}

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

li get(int l, int r)
{
    return get(r) - get(l - 1);
}

li dp[N];
int a[N], b[N], p[N];
int n, m;

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for(int i = 0; i < n; i++)
        scanf("%d", &p[i]);
    scanf("%d", &m);
    for(int i = 0; i < m; i++)
        scanf("%d", &b[i]);

    for(int i = 0; i < n; i++)
        dp[i] = -INF64;
    map<int, vector<int> > pos;
    for(int i = 0; i < n; i++)
        pos[a[i]].push_back(i);
    set<pair<int, int> > q;
    for(int i = 0; i < n; i++)
        q.insert(make_pair(a[i], i));
    
    for(auto x : pos[b[0]])
        dp[x] = p[x];
    while(!q.empty() && q.begin()->first <= b[0])
    {
        int k = q.begin()->second;
        q.erase(q.begin());
        if(p[k] > 0)
            inc(k, p[k]);
    }  

    for(int i = 1; i < m; i++)
    {
        int i1 = b[i - 1], i2 = b[i];
        vector<int> both_pos;
        for(auto x : pos[i1])
            both_pos.push_back(x);
        for(auto x : pos[i2])
            both_pos.push_back(x);
        li best = -INF64;
        int last = -1;
        sort(both_pos.begin(), both_pos.end());
        for(auto x : both_pos)
        {
            best += get(last + 1, x);
            last = x;
            if(a[x] == i1)
                best = max(best, dp[x]);
            else
                dp[x] = best + p[x];
        }
        while(!q.empty() && q.begin()->first <= i2)
        {
            int k = q.begin()->second;
            q.erase(q.begin());
            if(p[k] > 0)
                inc(k, p[k]);
        }
    }

    li best_dp = -INF64;
    for(int i = 0; i < n; i++)
        if(a[i] == b[m - 1])
            best_dp = max(best_dp, dp[i] + get(i + 1, n - 1));
    li ans = 0;
    for(int i = 0; i < n; i++)
        ans += p[i];
    ans -= best_dp;
    if(ans > li(1e15))
        puts("NO");
    else     
        printf("YES\n%lld\n", ans);
    
}

#include<bits/stdc++.h>

using namespace std;

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

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

typedef long double ld;
typedef long long li;

const ld PI = acos(-1.0);

struct comp 
{
    ld x, y;
    comp(ld x = .0, ld y = .0) : x(x), y(y) {}
    inline comp conj() { return comp(x, -y); }
};

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

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

inline comp operator *(const comp &a, const comp &b) 
{
    return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}

inline comp operator /(const comp &a, const ld &b) 
{
    return comp(a.x / b, a.y / b);
}

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

void precalc() 
{
    for(int st = 0; st < LOGN; st++) 
    {
        w[st].assign(1 << st, comp());
        for(int k = 0; k < (1 << st); k++) 
        {
            double ang = PI / (1 << st) * k;
            w[st][k] = comp(cos(ang), sin(ang));
        }
        
        rv[st].assign(1 << st, 0);
        if(st == 0) 
        {
            rv[st][0] = 0;
            continue;
        }
        int h = (1 << (st - 1));
        for(int k = 0; k < (1 << st); k++)
            rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    }
}

inline void fft(comp a[N], int n, int ln, bool inv) 
{
    for(int i = 0; i < n; i++) 
    {
        int ni = rv[ln][i];
        if(i < ni)
            swap(a[i], a[ni]);
    }
    
    for(int st = 0; (1 << st) < n; st++) 
    {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) 
        {
            for(int pos = k; pos < k + len; pos++) 
            {
                comp l = a[pos];
                comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]);
                
                a[pos] = l + r;
                a[pos + len] = l - r;
            }
        }
    }
    
    if(inv) for(int i = 0; i < n; i++)
        a[i] = a[i] / n;
}

comp aa[N];
comp bb[N];
comp cc[N];

inline void multiply(comp a[N], int sza, comp b[N], int szb, comp c[N], int &szc) 
{
    int n = 1, ln = 0;
    while(n < (sza + szb))
        n <<= 1, ln++;
    for(int i = 0; i < n; i++)
        aa[i] = (i < sza ? a[i] : comp());
    for(int i = 0; i < n; i++)
        bb[i] = (i < szb ? b[i] : comp());
        
    fft(aa, n, ln, false);
    fft(bb, n, ln, false);
    
    for(int i = 0; i < n; i++)
        cc[i] = aa[i] * bb[i];
        
    fft(cc, n, ln, true);
    
    szc = n;
    for(int i = 0; i < n; i++)
        c[i] = cc[i];
}

comp a[N];
comp b[N];
comp c[N];

vector<int> p_function(const vector<int>& v)
{
    int n = v.size();
    vector<int> p(n);
    for(int i = 1; i < n; i++)
    {
        int j = p[i - 1];
        while(j > 0 && v[j] != v[i])
            j = p[j - 1];
        if(v[j] == v[i])
            j++;
        p[i] = j;   
    }
    return p;
}

int p[26];
char buf[N];
string s, t;

int main()
{
    precalc();                  
    for(int i = 0; i < 26; i++)
    {
        scanf("%d", &p[i]);
        p[i]--;
    }
    scanf("%s", buf);
    s = buf;
    scanf("%s", buf);
    t = buf;

    int n = s.size();
    int m = t.size();
    vector<int> color(26, 0);
    vector<vector<int> > cycles;
    for(int i = 0; i < 26; i++)
    {
        if(color[i])
            continue;
        vector<int> cycle;
        int cc = cycles.size() + 1;
        int cur = i;
        while(color[cur] == 0)
        {
            cycle.push_back(cur);
            color[cur] = cc;
            cur = p[cur];
        }
        cycles.push_back(cycle);
    }

    vector<int> ans(m - n + 1);
    vector<int> s1, t1;
    for(int i = 0; i < n; i++)
        s1.push_back(color[int(s[i] - 'a')]);
    for(int i = 0; i < m; i++)
        t1.push_back(color[int(t[i] - 'a')]);
    vector<int> st = s1;
    st.push_back(0);
    for(auto x : t1)
        st.push_back(x);
    vector<int> pf = p_function(st);
    for(int i = 0; i < m - n + 1; i++)
        if(pf[2 * n + i] == n)
            ans[i] = 1;
    map<char, comp> m1, m2;
    for(auto cur : cycles)
    {
        int k = cur.size();
        for(int i = 0; i < k; i++)
        {
            ld ang1 = 2 * PI * i / k;
            ld ang2 = (PI - 2 * PI * i) / k;
            m1[char('a' + cur[i])] = comp(cosl(ang1), sinl(ang1));
            m2[char('a' + cur[i])] = comp(cosl(ang2), sinl(ang2));
        }
    }

    ld ideal = 0;
    for(int i = 0; i < n; i++)
        ideal += (m1[s[i]] * m2[s[i]]).x;
    reverse(s.begin(), s.end());
    for(int i = 0; i < n; i++)                  
        a[i] = m1[s[i]];                
    for(int i = 0; i < m; i++)
        b[i] = m2[t[i]];
    int szc;
    multiply(a, n, b, m, c, szc);
    for(int i = 0; i < m - n + 1; i++)
        if(fabsl(c[i + n - 1].x - ideal) > 0.01)
            ans[i] = 0;
    

    for(int i = 0; i < m - n + 1; i++)
        printf("%d", ans[i]);
    return 0;
}

for i in range(int(input())):
    n, k = map(int, input().split())
    print('YES' if k * k <= n and n % 2 == k % 2 else 'NO')

from sys import stdin, stdout

t = int(stdin.readline())
for _ in range(t):
    n = int(stdin.readline())
    used = [False for i in range(n)]
    v = -1
    for i in range(n):
        l = [int(x) - 1 for x in stdin.readline().split()][1:]
        for j in l:
            if not used[j]:
                used[j] = True
                break
        else:
            v = i
    if v == -1:
        stdout.write("OPTIMAL\n")
    else:
        u = used.index(False)
        stdout.write("IMPROVE\n" + str(v + 1) + " " + str(u + 1) + "\n")

n, m, _ = map(int, input().split())

print(2 * (n - 1) + (n + 1) * (m - 1))
print("U" * (n - 1) + "L" * (m - 1), end="")
for i in range(n):
    if i != 0:
        print("D", end="")
    if i % 2 == 0:
        print("R" * (m - 1), end="")
    else:
        print("L" * (m - 1), end="")

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

int n;
vector<int> p, c;

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

inline void solve() {
    vector<int> used(n, 0);
    
    int ans = INF;
    fore(st, 0, n) {
        if(used[st])
            continue;
        
        vector<int> cycle;
        int v = st;
        while(!used[v]) {
            used[v] = 1;
            cycle.push_back(v);
            v = p[v];
        }
        
        fore(step, 1, sz(cycle) + 1) {
            if(sz(cycle) % step != 0)
                continue;
            
            fore(s, 0, step) {
                bool eq = true;
                for(int pos = s; pos + step < sz(cycle); pos += step) {
                    if(c[cycle[pos]] != c[cycle[pos + step]])
                        eq = false;
                }
                if(eq) {
                    ans = min(ans, step);
                    break;
                }
            }
        }
    }
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    int tc; cin >> tc;
    
    while(tc--) {
        read();
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

MOD = 998244353
p = [1] * 200005
for i in range(1, 200005):
    p[i] = (p[i - 1] * 10) % MOD

n = int(input())
for i in range(1, n):
    res = 2 * 10 * 9 * p[n - i - 1]
    res += (n - 1 - i) * 10 * 9 * 9 * p[n - i - 2]
    print(res % MOD, end = ' ')
print(10)

#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

const int MOD = 998244353;
const int N = 500 * 1000 + 13;

int n, k, m;
pair<pt, int> q[N];

int ones[N];
int mx[N], sum[N];

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

int calc(int t) {
    memset(ones, 0, sizeof(ones));
    memset(mx, -1, sizeof(mx));
    
    forn(i, m) {
        int l = q[i].x.x, r = q[i].x.y;
        if (q[i].y & (1 << t)) {
            ones[l]++;
            ones[r + 1]--;
        } else {
            mx[r] = max(mx[r], l);
        }
    }
    
    int j = -1;
    forn(i, n) {
        int cur = 0;
        if (!ones[i]) {
            cur = sum[i];
            if (j == -1) cur = add(cur, 1);
            else cur = add(cur, -sum[j]);
        }
        
        sum[i + 1] = add(sum[i], cur);
        ones[i + 1] += ones[i];
        j = max(j, mx[i]);
    }
    
    return add(sum[n], j != -1 ? -sum[j] : 1);
}

int main() {
    scanf("%d%d%d", &n, &k, &m);
    forn(i, m) {
        scanf("%d%d%d", &q[i].x.x, &q[i].x.y, &q[i].y);
        --q[i].x.x; --q[i].x.y;
    }
    
    int ans = 1;
    forn(i, k) ans = (ans * 1ll * calc(i)) % MOD;
    printf("%d\n", ans);
}

#include<bits/stdc++.h>

using namespace std;

const int N = 8000043;
const int K = 15;
const int M = 1043;

int k;
char buf[N], buf2[M];
vector<string> t;
vector<int> c;
string s;

map<char, int> nxt[M];
int lnk[M];
int p[M];
char pchar[M];
map<char, int> go[M];
int term[M];
int ts = 1;
int A[M][K];
int F[M][K];
int dp[M];

int get_nxt(int x, char c)
{
    if(!nxt[x].count(c))
    {
        p[ts] = x;
        pchar[ts] = c;
        nxt[x][c] = ts++;
    }
    return nxt[x][c];
}

void add_string(int i)
{
    int cur = 0;
    for(auto x : t[i])
    {
        cur = get_nxt(cur, x);
    }
    term[cur] += c[i];
}

int get_go(int x, char c);

int get_lnk(int x)
{
    if(lnk[x] != -1)
        return lnk[x];
    if(x == 0 || p[x] == 0)
        return lnk[x] = 0;
    return lnk[x] = get_go(get_lnk(p[x]), pchar[x]);
}

int get_dp(int x)
{
    if(dp[x] != -1)
        return dp[x];
    dp[x] = term[x];
    if(get_lnk(x) != x)
        dp[x] += get_dp(get_lnk(x));
    return dp[x];
}

int get_go(int x, char c)
{
    if(go[x].count(c))
        return go[x][c];
    if(nxt[x].count(c))
        return go[x][c] = nxt[x][c];
    if(x == 0)
        return go[x][c] = 0;
    return go[x][c] = get_go(get_lnk(x), c);
}

void build_skip(const string& s, vector<int>& sA, vector<long long>& sF)
{                     
    sA = vector<int>(ts);
    for(int i = 0; i < ts; i++)
        sA[i] = i;
    sF = vector<long long>(ts);
    for(auto c : s)
    {
        int ci = int(c - 'a');
        for(int i = 0; i < ts; i++)
        {
            sF[i] += F[sA[i]][ci];
            sA[i] = A[sA[i]][ci];
        }
    }
}

long long solve(const string& s)
{
    long long BAD = (long long)(-1e18);

    vector<int> pos;
    for(int i = 0; i < s.size(); i++)
        if(s[i] == '?')
            pos.push_back(i);
    int cntQ = pos.size();
    vector<vector<int> > skip_A(cntQ + 1);
    vector<vector<long long> > skip_F(cntQ + 1);
    build_skip(s.substr(0, pos[0]), skip_A[0], skip_F[0]);
    for(int i = 1; i < cntQ; i++)
        build_skip(s.substr(pos[i - 1] + 1, pos[i] - pos[i - 1] - 1), skip_A[i], skip_F[i]);
    build_skip(s.substr(pos.back() + 1, s.size() - pos.back() - 1), skip_A[cntQ], skip_F[cntQ]);

    vector<vector<long long> > dp(1 << (K - 1), vector<long long>(ts, BAD));
    vector<int> used(1 << K);
    dp[0][skip_A[0][0]] = skip_F[0][0];
    queue<int> q;
    q.push(0);
    used[0] = 1;
    long long ans = BAD;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        int step = __builtin_popcount(k);
        if(step == cntQ)
        {
            for(int i = 0; i < ts; i++)
                ans = max(ans, dp[k][i]);
            continue;
        }
        for(int i = 0; i < K - 1; i++)
        {
            if(k & (1 << i)) continue;
            int nk = (k ^ (1 << i));
            if(used[nk] == 0)
            {
                used[nk] = 1;
                q.push(nk);
            }
            for(int j = 0; j < ts; j++)
            {
                if(dp[k][j] == BAD)
                    continue;
                int nj = get_go(j, char('a' + i));
                int newSt = skip_A[step + 1][nj];
                long long add = get_dp(nj) + skip_F[step + 1][nj];
                dp[nk][newSt] = max(dp[nk][newSt], dp[k][j] + add);
            }
        }
    }
    return ans;
}

int main()
{
    scanf("%d", &k);
    t.resize(k);
    c.resize(k);
    for(int i = 0; i < k; i++)
    {
        scanf("%s %d", buf2, &c[i]);
        t[i] = buf2;
    }    
    scanf("%s", buf);
    s = buf;

    for(int i = 0; i < k; i++)
        add_string(i);
    for(int i = 0; i < ts; i++)
    {
        lnk[i] = -1;
        dp[i] = -1;
    }
    for(int i = 0; i < ts; i++)
    {
        get_lnk(i);
        for(char c = 'a'; c <= 'o'; c++)
            get_go(i, c);
    }
    for(int i = 0; i < ts; i++)
        get_dp(i);                               
    for(int i = 0; i < ts; i++)
    {
        for(int j = 0; j < K; j++)
        {
            A[i][j] = get_go(i, char('a' + j));
            F[i][j] = dp[A[i][j]];
        }
    }   
    int n = s.size();
    vector<int> leftQ(n, -1);
    vector<int> rightQ(n, -1);
    for(int i = 0; i < n; i++)
    {
        if(i != 0)
            leftQ[i] = leftQ[i - 1];
        if(s[i] == '?')
            leftQ[i] = i;
    }
    for(int i = n - 1; i >= 0; i--)
    {
        if(i != n - 1)
            rightQ[i] = rightQ[i + 1];
        if(s[i] == '?')
            rightQ[i] = i;
    }
    vector<int> bad(n, 0);
    
    if(leftQ.back() == -1)
        bad = vector<int>(n, 1);

    long long ans = 0;
    int curSt = 0;
    string news = "";
    for(int i = 0; i < n; i++)
    {
        int ci = (s[i] == '?' ? 14 : int(s[i] - 'a'));
        if(bad[i])
            ans += F[curSt][ci];
        curSt = A[curSt][ci];
        if(!bad[i])
            news.push_back(s[i]);
        else if(i != 0 && !bad[i - 1])
            news.push_back('o');
    }                    
    if(!news.empty())
        ans += solve(news);
    printf("%lld\n", ans);
}

for i in range(int(input())):
    n, m = map(int, input().split())
    print('YES' if n % m == 0 else 'NO')

for t in range(int(input())):
    n = input()
    print(*sorted(map(int, input().split()))[::-1])

fun main() {
    val T = readLine()!!.toInt()
    testCases@for (tc in 1..T) {
        val (_, k) = readLine()!!.split(' ').map { it.toLong() }
        val a = readLine()!!.split(' ').map { it.toLong() }.toLongArray()

        var maxPower = 1L
        while (maxPower < 1e16.toLong())
            maxPower *= k

        while (maxPower > 0) {
            val positions = a.withIndex().filter { it.value >= maxPower }.map { it.index }
            if (positions.isNotEmpty()) {
                if (positions.size > 1) {
                    println("NO")
                    continue@testCases
                }
                a[positions[0]] -= maxPower
            }
            maxPower /= k
        }
        if (a.max()!! > 0L) {
            println("NO")
            continue@testCases
        }
        println("YES")
    }
}

fun getMask(a: Long, k: Long): Long? {
    var (tmp, res) = listOf(a, 0L)
    var cnt = 0
    while (tmp > 0) {
        if (tmp % k > 1)
            return null
        res = res or ((tmp % k) shl cnt)
        tmp /= k
        cnt++
    }
    return res
}

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val (n, k) = readLine()!!.split(' ').map { it.toLong() }
        val a = readLine()!!.split(' ').map { getMask(it.toLong(), k) }
        val b = a.filterNotNull()
        if (b.size < n) {
            println("NO")
            continue
        } else {
            val res = b.reduce { acc, l -> if (acc < 0 || (acc and l) > 0) -1 else acc or l }
            println(if (res < 0) "NO" else "YES")
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200043;
const int MOD = 998244353;

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

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

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

int fact[N];

void precalc()
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

int C(int n, int k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}

int main() 
{
    precalc();
    int n, m;
    cin >> n >> m;
    int ans = 0;
    if(n > 2)
        ans = mul(C(m, n - 1), mul(n - 2, binpow(2, n - 3)));
    cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

const int N = 555;
int n, a[N];

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

int dp[N][N];

int calcDP(int l, int r) {
    assert(l < r);
    if(l + 1 == r)
        return dp[l][r] = a[l];
    if(dp[l][r] != 0)
        return dp[l][r];
    
    dp[l][r] = -1;
    fore(mid, l + 1, r) {
        int lf = calcDP(l, mid);
        int rg = calcDP(mid, r);
        if(lf > 0 && lf == rg)
            return dp[l][r] = lf + 1;
    }
    return dp[l][r];
}

int dp2[N];

inline void solve() {
    fore(i, 0, N)
        dp2[i] = INF;
    
    dp2[0] = 0;
    fore(i, 0, n) {
        fore(j, i + 1, n + 1) {
            if(calcDP(i, j) > 0)
                dp2[j] = min(dp2[j], dp2[i] + 1);
        }
    }
    cout << dp2[n] << endl;
}

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

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;
const int K = 5;

int x, y, z, n;
long long a[N];

typedef vector<vector<int> > state;
map<state, int> d;
int cnt;
int p;
vector<vector<int> > state_log;

int mex(const vector<int>& a)
{
    for(int i = 0; i < a.size(); i++)
    {
        bool f = false;
        for(auto x : a)
            if(x == i)
                f = true;
        if(!f)
            return i;
    }
    return a.size();
}

state go(state s)
{
    int f1 = mex({s[0][K - x], s[1][K - y], s[2][K - z]});
    int f2 = mex({s[0][K - x], s[2][K - z]});
    int f3 = mex({s[0][K - x], s[1][K - y]});
    state nw = s;
    nw[0].push_back(f1);
    nw[1].push_back(f2);
    nw[2].push_back(f3);
    for(int i = 0; i < 3; i++)
        nw[i].erase(nw[i].begin());
    return nw;
}

void precalc()
{
    d.clear();
    state cur(3, vector<int>(K, 0));
    cnt = 0;
    state_log.clear();
    while(!d.count(cur))
    {
        d[cur] = cnt;
        state_log.push_back({cur[0].back(), cur[1].back(), cur[2].back()});
        cur = go(cur);
        cnt++;
    }                   
    p = cnt - d[cur];
}

int get_grundy(long long x, int t)
{
    if(x < cnt)
        return state_log[x][t];
    else
    {
        int pp = cnt - p;
        x -= pp;
        return state_log[pp + (x % p)][t];
    }
}

void read()
{
    scanf("%d %d %d %d", &n, &x, &y, &z);
    for(int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
}                    

int check(int x, int y)
{
    return x == y ? 1 : 0;
}

void solve()
{
    precalc();
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans ^= get_grundy(a[i], 0);
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        ans ^= get_grundy(a[i], 0);
        res += check(ans, get_grundy(max(0ll, a[i] - x), 0));
        res += check(ans, get_grundy(max(0ll, a[i] - y), 1));
        res += check(ans, get_grundy(max(0ll, a[i] - z), 2));
        ans ^= get_grundy(a[i], 0);
    }
    printf("%d\n", res);
}

int main()
{
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++)
    {
        read();
        solve();
    }
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1000043;

map<char, int> nxt[N];
bool term[N];
int n, k;
char buf[3];
int dp[N];
int dict[N];

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

void build(int v, int l, int r)
{
    T[v] = int(1e9);
    if(l != r - 1)
    {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
    }
}

int getVal(int v)
{
    return T[v] + f[v];
}

void push(int v, int l, int r)
{
    T[v] += f[v];
    if(l != r - 1)
    {
        f[v * 2 + 1] += f[v];
        f[v * 2 + 2] += f[v];
    }
    f[v] = 0;
}

void upd(int v, int l, int r)
{
    if(l != r - 1)
    {
        T[v] = min(getVal(v * 2 + 1), getVal(v * 2 + 2));
    }
}

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

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

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

void dfs(int v, int d, int last)
{
    dp[v] = last + 1;
    if(term[v])
        dp[v] = min(dp[v], get(0, 0, n + 1, 0, d));
    setVal(0, 0, n + 1, d, dp[v] + 1);
    if(term[v])
        add(0, 0, n + 1, 0, d + 1, 1);
    for(auto x : nxt[v])
        dfs(x.second, d + 1, dp[v]);
    setVal(0, 0, n + 1, d, int(1e9));
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int p;
        scanf("%d %s", &p, buf);
        char c = buf[0];
        nxt[p][c] = i + 1;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++)
    {
        scanf("%d", &dict[i]);
        term[dict[i]] = true;
    }

    build(0, 0, n + 1);
    dfs(0, 0, -1);
    for(int i = 0; i < k; i++)
        printf("%d ", dp[dict[i]]);
    puts("");
}

for t in range(int(input())):
    print(input().strip('0').count('0'))

fun main() {
    val t = readLine()!!.toInt()
    for (tc in 1..t) {
        val (n, g, b) = readLine()!!.split(' ').map { it.toLong() }
        
        val needG = (n + 1) / 2
        var totalG = needG / g * (b + g)
        totalG += if (needG % g == 0L) -b else needG % g
        println(maxOf(n, totalG))
    }
}

#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)

void solve() {
    string s;
    cin >> s;

    vector<bool> used(26);
    used[s[0] - 'a'] = true;
    string t(1, s[0]);
        
    int pos = 0;
    for (int i = 1; i < sz(s); i++) {
        if (used[s[i] - 'a']) {
            if (pos > 0 && t[pos - 1] == s[i]) {
                pos--;
            } else if (pos + 1 < sz(t) && t[pos + 1] == s[i]) {
                pos++;
            } else {
                cout << "NO" << endl;
                return;
            }
        } else {
            if (pos == 0) {
                t = s[i] + t;
            } else if (pos == sz(t) - 1) {
                t += s[i];
                pos++;
            } else {
                cout << "NO" << endl;
                return;
            }
        }
        used[s[i] - 'a'] = true;
    }
        
    forn(i, 26) if (!used[i])
        t += char(i + 'a');
    cout << "YES" << endl << t << endl;
}

int main() {
    int tc;
    cin >> tc;
    
    forn(i, tc) solve();
}

from math import log2

for t in range(int(input())):
    n, m = map(int, input().split())
    c = [0] * 61
    s = 0
    for x in map(int, input().split()):
        c[int(log2(x))] += 1
        s += x

    if s < n:
        print(-1)
        continue

    i, res = 0, 0
    while i < 60:
        if (1<<i)&n != 0:
            if c[i] > 0:
                c[i] -= 1
            else:
                while i < 60 and c[i] == 0:
                    i += 1
                    res += 1
                c[i] -= 1
                continue
        c[i + 1] += c[i] // 2
        i += 1

    print(res)

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

string s, t;

inline bool read() {
    if(!(cin >> s >> t))
        return false;
    for(auto &c : s)
        c -= 'a';
    for(auto &c : t)
        c -= 'a';
    return true;
}

vector< vector<int> > nxt;

bool calc(const string &a, const string &b) {
    vector< vector<int> > dp(sz(a) + 1, vector<int>(sz(b) + 1, INF));
    dp[0][0] = 0;
    fore(i, 0, sz(a) + 1) fore(j, 0, sz(b) + 1) {
        if(dp[i][j] > sz(s))
            continue;
        
        int len = dp[i][j];
        if(i < sz(a) && nxt[len][a[i]] < INF) {
            dp[i + 1][j] = min(dp[i + 1][j], nxt[len][a[i]] + 1);
        }
        if(j < sz(b) && nxt[len][b[j]] < INF) {
            dp[i][j + 1] = min(dp[i][j + 1], nxt[len][b[j]] + 1);
        }
    }
    return dp[sz(a)][sz(b)] < INF;
}

inline void solve() {
    nxt.assign(sz(s) + 1, vector<int>(26, INF));
    for(int i = sz(s) - 1; i >= 0; i--) {
        nxt[i] = nxt[i + 1];
        nxt[i][s[i]] = i;
    }
    
    for(int i = 0; i < sz(t); i++) {
        if(calc(t.substr(0, i), t.substr(i, sz(t)))) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    int tc; cin >> tc;
    
    while(tc--) {
        read();
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define forr(i, r, l) for (int i = int(r) - 1; i >= int(l); --i)

typedef pair<int, int> pt;

const int M = 310;
const int N = 2000 * 1000 + 13;

int n, m, q;
int a[M][M];

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

bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int p[M * M], rk[M * M];

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

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);
    p[b] = a;
    rk[a] += rk[b];
    return true;
}

int dif[N];
vector<pt> add[N], del[N];

void recalc(const vector<pt>& ev, int coeff)  {
    forn(i, n) forn(j, m) a[i][j] = 0;
    forn(i, n * m) p[i] = i, rk[i] = 1;
        
    for (auto it : ev) {
        int cur = 1;
        int x = it.x / m, y = it.x % m;
        a[x][y] = 1;
        
        forn(k, 4) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (in(nx, ny) && a[nx][ny] == 1)
                cur -= unite(nx * m + ny, x * m + y);
        }
        
        dif[it.y] += cur * coeff;
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    int clrs = 1;
    forn(i, q) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        --x; --y;
        if (a[x][y] == c) continue;
        clrs = c + 1;
        add[c].pb(mp(x * m + y, i));
        del[a[x][y]].pb(mp(x * m + y, i));
        a[x][y] = c;
    }
    
    forn(x, n) forn(y, m)
        del[a[x][y]].pb(mp(x * m + y, q));
    
    forn(i, clrs) reverse(all(del[i]));
    
    forn(i, clrs) recalc(add[i], +1);
    forn(i, clrs) recalc(del[i], -1);
    
    int cur = 1;
    forn(i, q) {
        cur += dif[i];
        printf("%d\n", cur);
    }
}

#include<bits/stdc++.h>

using namespace std;

const int N = 150043;

typedef pair<long long, long long> func;

func T[4 * N];
bool usedT[4 * N];

void clear(int v, int l, int r)
{
    if(!usedT[v]) return;
    usedT[v] = false;
    T[v] = make_pair(0ll, 0ll);
    if(l < r - 1)
    {
        int m = (l + r) / 2;
        clear(v * 2 + 1, l, m);
        clear(v * 2 + 2, m, r);
    }
}

long long eval(func f, int x)
{
    return f.first * x + f.second;
}

long long get(int v, int l, int r, int x)
{
    long long ans = eval(T[v], x);
    if(l < r - 1)
    {
        int m = (l + r) / 2;
        if(m > x)
            ans = max(ans, get(v * 2 + 1, l, m, x));
        else
            ans = max(ans, get(v * 2 + 2, m, r, x));
    }
    return ans;
}

void upd(int v, int l, int r, func f)
{
    usedT[v] = true;
    int m = (l + r) / 2;
    bool need_swap = eval(f, m) > eval(T[v], m);
    if(need_swap)
        swap(T[v], f);
    if(l == r - 1)
        return;
    if(eval(f, l) > eval(T[v], l))
        upd(v * 2 + 1, l, m, f);
    else
        upd(v * 2 + 2, m, r, f);
}

long long ans = 0;

void update_ans(vector<vector<func> > heads, vector<vector<func> > tails)
{
    int n = heads.size();
    for(int i = 0; i < n; i++)
    {
        for(auto x : heads[i])
            ans = max(ans, get(0, 0, N, x.first) + x.second);
        for(auto x : tails[i])
            upd(0, 0, N, x);
    }
    clear(0, 0, N);
}

int a[N];
vector<int> g[N];
int n;
bool used[N];
int siz[N];

void dfs1(int x, int p = -1)
{
    if(used[x]) return;
    siz[x] = 1;
    for(auto to : g[x])
    {                    
        if(!used[to] && to != p)
        {
            dfs1(to, x);
            siz[x] += siz[to];
        }
    }
}

pair<int, int> c;
int S = 0;

void find_centroid(int x, int p = -1)
{
    if(used[x]) return;
    int mx = 0;
    for(auto to : g[x])
    {
        if(!used[to] && to != p)
        {
            find_centroid(to, x);
            mx = max(mx, siz[to]);
        }
    }
    if(p != -1)
        mx = max(mx, S - siz[x]);
    c = min(c, make_pair(mx, x));
}

void dfs_heads(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += curadd;
    sink.push_back(make_pair(cnt, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_heads(to, v, cnt, cursum, curadd, sink);
}

void dfs_tails(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += a[v] * 1ll * cnt;
    sink.push_back(make_pair(curadd, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_tails(to, v, cnt, cursum, curadd, sink);
}

void centroid(int v)
{
    if(used[v]) return;
    dfs1(v);
    S = siz[v];
    c = make_pair(int(1e9), -1);
    find_centroid(v);
    int C = c.second;
    used[C] = 1;
    vector<vector<func> > heads, tails;
    for(auto to : g[C])
        if(!used[to])
        {
            heads.push_back(vector<func>());
            dfs_heads(to, C, 1, a[C], a[C], heads.back());
            tails.push_back(vector<func>());
            dfs_tails(to, C, 0, 0, 0, tails.back());
        }
    heads.push_back(vector<func>({{1, a[C]}}));
    tails.push_back(vector<func>({{0, 0}}));
    update_ans(heads, tails);
    reverse(heads.begin(), heads.end());
    reverse(tails.begin(), tails.end());
    update_ans(heads, tails);
    for(auto to : g[C])
        centroid(to);
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);    
    }
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    centroid(0);
    printf("%lld\n", ans);
}

t = int(input())
for i in range(t):
    n = int(input())
    if(n % 2 == 1):
        print(7, end='')
        n -= 3
    while(n > 0):
        print(1, end='')
        n -= 2
    print()

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

int n, x;
string s;

inline bool read() {
	if(!(cin >> n >> x >> s))
		return false;
	return true;
}

inline void solve() {
	int ans = 0;
	bool infAns = false;
	
	int cntZeros = (int)count(s.begin(), s.end(), '0');
	int total = cntZeros - (n - cntZeros);
	
	int bal = 0;
	for(int i = 0; i < n; i++) {
		if(total == 0) {
			if(bal == x)
				infAns = true;
		}
		else if(abs(x - bal) % abs(total) == 0) {
			if((x - bal) / total >= 0)
				ans++;
		}
		
		if(s[i] == '0')
			bal++;
		else
			bal--;
	}
	
	if(infAns) ans = -1;
	cout << ans << endl;
}

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

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

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

int tc;
string s, t;
int nxt[N][26];

int main() {
    cin >> tc;
    while(tc--){
        cin >> s >> t;
        for(int i = 0; i < s.size() + 5; ++i)
            for(int j = 0; j < 26; ++j)
                nxt[i][j] = INF;
    	
        for(int i = int(s.size()) - 1; i >= 0; --i){
            for(int j = 0; j < 26; ++j)
                nxt[i][j] = nxt[i + 1][j];
            nxt[i][s[i] - 'a'] = i;
        }    
    
        int res = 1, pos = 0;
        for(int i = 0; i < t.size(); ++i){
            if(pos == s.size()){
                pos = 0;
                ++res;
            }
            if(nxt[pos][t[i] - 'a'] == INF){
                pos = 0; 
                ++res;
    		}
    		if(nxt[pos][t[i] - 'a'] == INF && pos == 0){
                res = INF;
                break;
            }    
            pos = nxt[pos][t[i] - 'a'] + 1;
            
        }
    
        if(res >= INF) cout << -1 << endl;
        else cout << res << endl;
    }
    return 0;
}

fun gcd(a : Long, b : Long) : Long {
    return if (a == 0L) b else gcd(b % a, a)
}
fun phi(a : Long) : Long {
    var (tmp, ans) = listOf(a, a)
    var d = 2L
    while (d * d <= tmp) {
        var cnt = 0
        while (tmp % d == 0L) {
            tmp /= d
            cnt++
        }
        if (cnt > 0) ans -= ans / d
        d++
    }
    if (tmp > 1L) ans -= ans / tmp
    return ans
}

fun main() {
    val t = readLine()!!.toInt()
    for (tc in 1..t) {
        val (a, m) = readLine()!!.split(' ').map { it.toLong() }
        println(phi(m / gcd(a, m)))
    }
}

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

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

int n;
int p[N];
int rp[N];
int a[N];

long long b[N];
long long t[4 * N];
long long add[4 * N];

void build(int v, int l, int r){
	if(r - l == 1){
		t[v] = b[l];
		return;
	}

	int mid = (l + r) / 2;	
	build(v * 2 + 1, l, mid);
	build(v * 2 + 2, mid, r);
	t[v] = min(t[v * 2 + 1], t[v * 2 + 2]); 
}

void push(int v, int l, int r){
	if(add[v] != 0){
		if(r - l > 1)
			for(int i = v+v+1; i < v+v+3; ++i){
				add[i] += add[v];
				t[i] += add[v];
			}
		add[v] = 0;
	}
}

void upd(int v, int l, int r, int L, int R, int x){
	if(L >= R) return;
	if(l == L && r == R){
		add[v] += x;
		t[v] += x;
		push(v, l, r);
		return;
	}
	
	push(v, l, r);
	int mid = (l + r) / 2;
	upd(v * 2 + 1, l, mid, L, min(mid, R), x);
	upd(v * 2 + 2, mid, r, max(mid, L), R, x);

	t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}

void upd(int l, int r, int x){
	upd(0, 0, n, l, r, x);
}

long long get(int v, int l, int r, int L, int R){
	if(L >= R) return 1e18;

	push(v, l, r);
	if(l == L && r == R)
		return t[v];

	int mid = (l + r) / 2;
	return min(get(v * 2 + 1, l, mid, L, min(R, mid)), 
		   get(v * 2 + 2, mid, r, max(L, mid), R));		
}

long long get(int l, int r){
	return get(0, 0, n, l, r);
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", p + i);
        --p[i];
        rp[p[i]] = i;
	}
	for(int i = 0; i < n; ++i)
		scanf("%d", a + i);
	
	b[0] = a[0];
	for(int i = 1; i < n; ++i)
		b[i] = a[i] + b[i - 1];
	build(0, 0, n);
	
	long long res = get(0, n - 1);
	//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
	for(int i = 0; i < n; ++i){
	    int pos = rp[i];
		upd(pos, n, -a[pos]);
		upd(0, pos, a[pos]);
		res = min(res, get(0, n - 1));
		//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
	}
	
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

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

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

typedef vector<int> poly;

void norm(poly& p)
{
    while(p.size() > 0 && p.back() == 0)
        p.pop_back();
}

poly operator +(const poly& a, const poly& b)
{
    poly c = a;
    while(c.size() < b.size()) c.push_back(0);
    for(int i = 0; i < b.size(); i++) c[i] = add(c[i], b[i]);
    norm(c);
    return c;
}

poly operator +(const poly& a, int b)
{
    return a + poly(1, b);
}

poly operator +(int a, const poly& b)
{
    return b + a;
}

poly operator *(const poly& a, int b)
{
    poly c = a;                               
    for(int i = 0; i < c.size(); i++) c[i] = mul(c[i], b);
    norm(c);
    return c;
}

poly operator /(const poly& a, int b)
{   
    return a * inv(b);
}

poly operator *(const poly& a, const poly& b)
{
    poly c(a.size() + b.size() - 1);
    for(int i = 0; i < a.size(); i++)
        for(int j = 0; j < b.size(); j++)
            c[i + j] = add(c[i + j], mul(a[i], b[j]));

    norm(c);
    return c;
}

poly interpolate(const vector<int>& x, const vector<int>& y)
{
    int n = int(x.size()) - 1;
    vector<vector<int> > f(n + 1);
    f[0] = y;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= n - i; j++)
            f[i].push_back(divide(add(f[i - 1][j + 1], -f[i - 1][j]), add(x[i + j], -x[j])));
    
    poly cur = poly(1, 1);
    poly res;
    for(int i = 0; i <= n; i++)
    {
        res = res + cur * f[i][0];
        cur = cur * poly({add(0, -x[i]), 1});
    }

    return res;
}

int eval(const poly& a, int x)
{
    int res = 0;
    for(int i = int(a.size()) - 1; i >= 0; i--)
        res = add(mul(res, x), a[i]);
    return res;
}

poly sumFromL(const poly& a, int L, int n)
{
    vector<int> x;
    for(int i = 0; i <= n; i++)
        x.push_back(L + i);
    vector<int> y;
    int cur = 0;
    for(int i = 0; i <= n; i++)
    {
        cur = add(cur, eval(a, x[i]));
        y.push_back(cur);
    }
    return interpolate(x, y);
}

int sumOverSegment(const poly& a, int L, int R)
{
    return eval(sumFromL(a, L, a.size()), R - 1);
}

int main() {
    int n;
    cin >> n;
    vector<int> L(n), R(n);
    for(int i = 0; i < n; i++)
    {
        cin >> L[i] >> R[i];
        R[i]++;
    }
    reverse(L.begin(), L.end());
    reverse(R.begin(), R.end());

    vector<int> coord = {0, MOD - 2};
    for(int i = 0; i < n; i++)
    {
        coord.push_back(L[i]);
        coord.push_back(R[i]);
    }
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    vector<int> cL = coord, cR = coord;
    cL.pop_back();
    cR.erase(cR.begin());
    int cnt = coord.size() - 1;
    vector<poly> cur(cnt);
    for(int i = 0; i < cnt; i++)
        if(cL[i] >= L[0] && cR[i] <= R[0])
            cur[i] = poly(1, inv(R[0] - L[0]));
    for(int i = 1; i < n; i++)
    {
        vector<poly> nxt(cnt);        
        int curSum = 0;
        for(int j = 0; j < cnt; j++)
        {
            nxt[j] = sumFromL(cur[j], cL[j], i) + curSum;
            curSum = add(curSum, sumOverSegment(cur[j], cL[j], cR[j]));    
        }
        for(int j = 0; j < cnt; j++)
            nxt[j] = nxt[j] * (cL[j] >= L[i] && cR[j] <= R[i] ? inv(R[i] - L[i]) : 0);
        cur = nxt;
    }
    int ans = 0;
    for(int i = 0; i < cnt; i++)
        ans = add(ans, sumOverSegment(cur[i], cL[i], cR[i]));

    cout << ans << endl;
}