for i in range(int(input())):
	print(len(input()))

#include<bits/stdc++.h>

using namespace std;

int main() {
	int t; cin >> t;
	while (t--) {
		int x; cin >> x;
		
		int steps = 0;
		while (steps * (steps + 1) < 2 * x)
			steps++;
		
		if (steps * (steps + 1) / 2 == x + 1)
			steps++;
		cout << steps << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int x, y;
	cin >> x >> y;
	cout << x - 1 << " " << y << endl;	
}

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

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n, x;
        cin >> n >> x;
        vector<int> a(n);
        for(int i = 0; i < n; i++)
            cin >> a[i];
        if(is_sorted(a.begin(), a.end()))
        {
            cout << 0 << endl;
            continue;
        }
        vector<vector<int>> dp(n, vector<int>(501, int(1e9)));
        for(int i = 0; i < n; i++)
        {
            if(a[i] > x && (i == 0 || a[i - 1] <= x))
                dp[i][x] = 1;
            if(i < n - 1 && a[i] > a[i + 1])
                break;
        }
        int ans = int(1e9);
        for(int i = 0; i < n; i++)
            for(int j = 0; j <= 500; j++)
            {
                if(dp[i][j] == int(1e9))
                    continue;
                if(i == n || (j <= a[i + 1] && is_sorted(a.begin() + i + 1, a.end())))
                    ans = min(ans, dp[i][j]);
                bool good = true;
                for(int k = i + 1; k < n; k++)
                {
                    int pr = k == i + 1 ? j : a[k - 1];
                    if(good && a[i] >= pr && a[i] < a[k])
                        dp[k][a[i]] = min(dp[k][a[i]], dp[i][j] + 1);
                    good &= a[k] >= pr;
                }
            }
        if(ans == int(1e9))
            ans = -1;
        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;

int n, x;
vector<int> a;

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

inline void solve() {
	vector<int> sf(n + 1, 0);
	sf[n] = sf[n - 1] = 1;
	for (int i = n - 2; i >= 0; i--) {
		if (a[i] <= a[i + 1])
			sf[i] = sf[i + 1];
	}
	
	int ans = 0;
	int uk = 0;
	while (true) {
		int np = uk;
		while (np < n && a[np] <= x)
			np++;
		fore (i, uk, np) {
			if (i == 0) continue;
			if (a[i - 1] > a[i]) {
				cout << -1 << endl;
				return;
			}
		}
		if (sf[np])
			break;
		
		assert(a[np] > x);
		swap(a[np], x);
		ans++;
		uk = np;
	}
	cout << ans << endl;
}

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

#include<bits/stdc++.h>

using namespace std;

#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<li, li> pt;

const li INF64 = li(1e18);

pt p[4];

inline bool read() {
	fore (i, 0, 4) {
		if(!(cin >> p[i].x >> p[i].y))
			return false;
	}
	return true;
}

inline void solve() {
	li ans = INF64;
	fore (st, 0, 2) {
		fore (idx1, 0, 4) fore (idx2, 0, 4) fore (idy1, 0, 4) {
			li x1 = p[idx1].x;
			li x2 = p[idx2].x;
			li y1 = p[idy1].y;
			
			if (x1 > x2)
				continue;
			
			for (int k = -1; k <= 1; k += 2) {
				li y2 = y1 + k * abs(x1 - x2);
				
				vector<pt> fp = { {x1, y1}, {x2, y1}, {x2, y2}, {x1, y2} };
				sort(fp.begin(), fp.end());
				
				do {
					li cur = 0;
					fore (i, 0, 4)
						cur += abs(fp[i].x - p[i].x) + abs(fp[i].y - p[i].y);
						
					ans = min(ans, cur);
				} while(next_permutation(fp.begin(), fp.end()));
			}
		}
		
		fore (i, 0, 4)
			swap(p[i].x, p[i].y);
	}
	cout << ans << endl;
}

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

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

const li INF64 = li(1e18);

pt p[4];

inline bool read() {
	fore (i, 0, 4) {
		if(!(cin >> p[i].x >> p[i].y))
			return false;
	}
	return true;
}

li len(const pt &a) {
	assert(a.y >= a.x);
	return a.y - a.x;
}
pt getSeg(li a, li b) {
	return { min(a, b), max(a, b) };
}
pt getOpt(const pt &a, const pt &b) {
	return {
		max({ a.x - b.y, b.x - a.y, 0LL }),
		max({ b.y - a.x, a.y - b.x, 0LL })
	};
}

inline void solve() {
	li ans = INF64;
	
	vector<int> id = { 0, 1, 2, 3 };
	do {
		li cur = 0;
		auto x1 = getSeg(p[id[0]].x, p[id[3]].x);
		auto x2 = getSeg(p[id[1]].x, p[id[2]].x);
		
		cur += len(x1) + len(x2);
		pt xSeg = getOpt(x1, x2);
		
		auto y1 = getSeg(p[id[0]].y, p[id[1]].y);
		auto y2 = getSeg(p[id[2]].y, p[id[3]].y);
		
		cur += len(y1) + len(y2);
		pt ySeg = getOpt(y1, y2);
		
		li is = min(xSeg.y, ySeg.y) - max(xSeg.x, ySeg.x);
		cur += 2 * max(0LL, -is);
		
		ans = min(ans, cur);
	}
	while (next_permutation(id.begin(), id.end()));
	
	cout << ans << endl;
}

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

#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int n, k;
string s;
string dp[N];

void solve() {
	cin >> n >> k >> s;
	for (int i = 1; i <= n; i++)
		dp[i] = char('z' + 1);
	for (int i = 0; i < n; i++) {
		int c = s[i] - 'a';
		int nc = min({c, (c + 1) % k, (c + k - 1) % k});
		dp[i + 1] = min(dp[i + 1], dp[i] + char('a' + nc));
		if (i > 0) {
			dp[i + 1] = min(dp[i + 1], dp[i - 1] + char('a' + nc) + s[i - 1]);
			dp[i + 1] = min(dp[i + 1], dp[i].substr(0, i - 1) + s[i] + dp[i].back());
		}
		if (i > 1) {
			dp[i + 1] = min(dp[i + 1], dp[i - 1].substr(0, i - 2) + s[i] + dp[i - 1].back() + s[i - 1]);
		}
	}
	cout << dp[n] << endl;
}

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

#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 long long INF = 1e18;

struct op{
	string tp;
	int y, v, to;
};

struct addmap{
	long long add;
	map<int, long long> val;
	multiset<long long> mn;
};

void reset(addmap &a, int x, long long val){
	if (a.val.count(x))
		a.mn.erase(a.mn.find(a.val[x]));
	a.val[x] = val - a.add;
	a.mn.insert(val - a.add);
}

int main() {
	int n, s;
	scanf("%d%d", &n, &s);
	static char buf[10];
	op a;
	vector<addmap> st;
	st.push_back({});
	st.back().val[0] = 0;
	st.back().add = 0;
	st.back().mn.insert(0);
	forn(i, n){
		scanf("%s", buf);
		a.tp = buf;
		if (a.tp == "set"){
			scanf("%d%d", &a.y, &a.v);
			assert(!st.back().mn.empty());
			long long mn = st.back().add + *st.back().mn.begin();
			st.back().add += a.v;
			if (a.y != s) reset(st.back(), a.y, mn);
		}
		else if (a.tp == "if"){
			scanf("%d", &a.y);
			long long val = INF;
			if (st.back().val.count(a.y)){
				val = st.back().val[a.y] + st.back().add;
				st.back().mn.erase(st.back().mn.find(st.back().val[a.y]));
				st.back().val.erase(a.y);
			}
			st.push_back({});
			reset(st.back(), a.y, val);
			st.back().add = 0;
		}
		else{
			if (st[int(st.size()) - 1].val.size() > st[int(st.size()) - 2].val.size())
				swap(st[int(st.size()) - 1], st[int(st.size()) - 2]);
			addmap& v = st[int(st.size()) - 2];
			for (auto it : st.back().val){
				if (!v.val.count(it.x) || v.val[it.x] + v.add > it.y + st.back().add){
					if (v.val.count(it.x))
						v.mn.erase(v.mn.find(v.val[it.x]));
					v.val[it.x] = it.y + st.back().add - v.add;
					v.mn.insert(it.y + st.back().add - v.add);
				}
			}
			st.pop_back();
		}
	}
	printf("%lld\n", *st.back().mn.begin() + st.back().add);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int x, y;
        cin >> x >> y;
        int ans = max(x, y) * 2 - 1;
        if(x == y) ans++;
        cout << ans << endl;
    }
}

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

        val k = maxOf(a.max()!!, (a.sum() + n - 2) / (n - 1))
        println(k * (n - 1) - a.sum())
    }
}

def calc(s, x, y):
	bal, cnt = 0, 0
	for c in s:
		if c == y:
			if bal > 0:
				bal -= 1
				cnt += 1
		elif c == x:
			bal += 1
	return cnt

for _ in range(int(input())):
	s = input()
	print(calc(s, '(', ')') + calc(s, '[', ']'))

#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 ans = 1;
    while(y > 0)
    {
        if(y % 2 == 1)
            ans = mul(ans, x);
        x = mul(x, x);
        y /= 2;
    }
    return ans;
}

int divide(int x, int y)
{
    return mul(x, binpow(y, MOD - 2));
}

int main()
{
    int n;
    cin >> n;
    vector<int> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;
    for(int i = 2; i <= n; i++)
        fib[i] = add(fib[i - 1], fib[i - 2]);
    cout << divide(fib[n], binpow(2, n)) << endl;    
}

#include <bits/stdc++.h>

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

using namespace std;

struct seg{
	int l, r;
};

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<seg> a(m);
	forn(i, m){
		cin >> a[i].l >> a[i].r;
		--a[i].l;
	}
	sort(a.begin(), a.end(), [](const seg &a, const seg &b){
		return a.l + a.r < b.l + b.r;
	});
	vector<int> su(m + 1);
	forn(i, n - k + 1){
		int cur = 0;
		for (int j = m - 1; j >= 0; --j){
			cur += max(0, min(i + k, a[j].r) - max(i, a[j].l));
			su[j] = max(su[j], cur);
		}
	}
	int ans = su[0];
	forn(i, n - k + 1){
		int cur = 0;
		forn(j, m){
			cur += max(0, min(i + k, a[j].r) - max(i, a[j].l));
			ans = max(ans, cur + su[j + 1]);
		}
	}
	cout << ans << endl;
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

typedef long long li;
typedef 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;

int n, q;
vector<li> cnt;

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

inline void solve() {
	fore (qs, 0, q) {
		int tp, pos;
		li val;
		cin >> tp >> pos >> val;
		if (tp == 1) {
			cnt[pos] = val;
		} else {
			li small = 0, cur = 0;
			fore (i, 0, pos + 1) {
				small += cnt[i] * ((1ll << i) - 1);
				val -= cnt[i];
			}
			if (val <= 0) {
				cout << 0 << '\n';
				continue;
			}
			
			int id = pos + 1;
			while (id < n) {
				li add = 1ll << (id - pos);
				li need = min(val / add, cnt[id]);
				cur += need * (add - 1);
				val -= need * add;
				small += need * add * ((1ll << pos) - 1);
				
				if (need == cnt[id])
					id++;
				else
					break;
			}
			if (val <= 0) {
				cout << cur << '\n';
				continue;
			}
			if (id >= n) {
				cout << (val > small ? -1 : cur + val) << '\n';
				continue;
			}
			
			li ans = INF64;
			while (id > pos) {
				if (small >= val)
					ans = min(ans, cur + val);
				cur++;
				id--;
				li add = 1ll << (id - pos);
				if (val >= add) {
					cur += add - 1;
					val -= add;
					small += add * ((1ll << pos) - 1);
				}
			}
			assert(val <= 0);
			cout << min(ans, cur) << 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>

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

using namespace std;

int n;
vector<vector<int>> g;

vector<int> h, pcd, d;
vector<vector<int>> st, vals;
vector<int> a;
 
int dfs(int v, int s, int &cd, int p = -1){
	int sum = 1;
	for (int u : g[v]) if (h[u] == -1 && u != p)
		sum += dfs(u, s, cd, v);
	if (cd == -1 && (2 * sum >= s || p == -1))
		cd = v;
	return sum;
}
 
void build(int v, int s, int d, int p = -1){
	int cd = -1;
	dfs(v, s, cd);
	h[cd] = d;
	pcd[cd] = p;
	for (int u : g[cd]) if (h[u] == -1)
		build(u, s / 2, d + 1, cd);
}

vector<char> cur;

void calcd(int v, int p = -1){
	for (int u : g[v]) if (u != p && cur[u]){
		d[u] = d[v] + 1;
		calcd(u, v);
	}
}

vector<vector<int>> dist;

void init(){
	a.resize(n, -1);
	int k;
	scanf("%d", &k);
	queue<int> q;
	forn(i, k){
		int v;
		scanf("%d", &v);
		--v;
		q.push(v);
		a[v] = 0;
	}
	while (!q.empty()){
		int v = q.front();
		q.pop();
		for (int u : g[v]) if (a[u] == -1){
			a[u] = a[v] + 1;
			q.push(u);
		}
	}
	h.resize(n, -1);
	pcd.resize(n);
	build(0, n, 0);
	st.resize(n);
	vector<int> nd(n);
	forn(v, n){
		int u = v;
		while (u != -1){
			st[u].push_back(v);
			if (pcd[u] != -1)
				nd[pcd[u]] = max(nd[pcd[u]], nd[u] + 1);
			u = pcd[u];
		}
	}
	cur.resize(n);
	vals.resize(n);
	dist.resize(n);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&nd](int x, int y){
		return nd[x] < nd[y];
	});
	d.resize(n);
	for (int v : ord){
		for (int u : st[v]) cur[u] = true;
		d[v] = 0;
		calcd(v);
		int mx = 0;
		for (int u : st[v]) mx = max(mx, d[u]);
		vals[v].resize(mx + 1, 0);
		for (int u : st[v]) vals[v][d[u]] = max(vals[v][d[u]], a[u]);
		forn(j, mx) vals[v][j + 1] = max(vals[v][j + 1], vals[v][j]);
		for (int u : st[v]) cur[u] = false;
		for (int u : st[v]) dist[u].push_back(d[u]);
	}
}

bool check(int v, int x){
	for (int i = 0, u = v; u != -1; u = pcd[u], ++i)
		if (x - dist[v][i] >= 0 && vals[u][min(int(vals[u].size()) - 1, x - dist[v][i])] > x)
			return true;
	return false;
}

int main() {
	scanf("%d", &n);
	g.resize(n);
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	init();
	forn(v, n){
		int res = 0;
		int l = 0, r = n;
		while (l <= r){
			int m = (l + r) / 2;
			if (check(v, m)){
				res = m + 1;
				l = m + 1;
			}
			else{
				r = m - 1;
			}
		}
		printf("%d ", res);
	}
	puts("");
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int LN = 18;

vector<int> g[N];
vector<int> dist[N];
int sz[N];
int par[N];
bool used[N];
int max_dist[N];
vector<int> val[N];

int calc_size(int x, int p = -1)
{
    sz[x] = 1;
    for(auto y : g[x])
        if(y != p && !used[y])
            sz[x] += calc_size(y, x);
    return sz[x];   
}

int find_centroid(int x, int p, int s)
{
    int ans = -1;
    bool good = true;
    for(auto y : g[x])
        if(y != p && !used[y])
            good &= sz[y] * 2 <= s;
        else if(y == p && !used[y])
            good &= (s - sz[x]) * 2 <= s;
    if(good)
        ans = x;
    for(auto y : g[x])
        if(y != p && !used[y])
            ans = max(ans, find_centroid(y, x, s));
    return ans;
}

void calc_dist(int x, int p, int d, int s)
{
    dist[x].push_back(d);
    for(auto y : g[x])
        if(y != p && !used[y])
            calc_dist(y, x, d + 1, s);
    max_dist[s] = max(max_dist[s], d);  
}

int decomposition(int v)
{
    calc_size(v);
    int c = find_centroid(v, v, sz[v]);
    used[c] = true;
    for(auto y : g[c])
        if(!used[y])
        {
            par[decomposition(y)] = c;
        }
    used[c] = false;
    calc_dist(c, c, 0, c); 
    return c;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    decomposition(0);
    for(int i = 0; i < n; i++)
        val[i].resize(max_dist[i] + 1);    
    int k;
    scanf("%d", &k);
    vector<int> d(n, int(1e9));
    queue<int> q;
    for(int i = 0; i < k; i++)
    {
        int x;
        scanf("%d", &x);
        --x;
        q.push(x);
        d[x] = 0;
    }
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(auto y : g[x])
            if(d[y] > d[x] + 1)
            {
                q.push(y);
                d[y] = d[x] + 1;
            }
    }
    for(int i = 0; i < n; i++)
    {
        if(d[i] == 0) continue;
        
        int curc = i;
        for(int j = 0; j < dist[i].size(); j++)
        {
            int dd = dist[i][j];
            if(dd > d[i] - 1)
            {
                curc = par[curc];
                continue;
            }
            dd = d[i] - 1 - dd;
            if(dd >= val[curc].size())
                dd = val[curc].size() - 1; 
            val[curc][dd] = max(val[curc][dd], d[i]);
            curc = par[curc];
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = max_dist[i]; j >= 1; j--)
            val[i][j - 1] = max(val[i][j], val[i][j - 1]);
    for(int i = 0; i < n; i++)
    {
        int ans = 0; 
        int curc = i;
        for(int j = 0; j < dist[i].size(); j++)
        {
            int dd = dist[i][j];
            ans = max(ans, val[curc][dd]);
            curc = par[curc];
        }
        if(d[i] == 0)
            ans = 0;
        printf("%d%c", ans, " \n"[i == n - 1]);
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (l, r) = readLine()!!.split(' ').map { it.toInt() }
        println(if (2 * l > r) "YES" else "NO");
    }
}

#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())

const int INF = int(1e9);

int n;
string s;

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

int cntSame(const string &s) {
	int ans = 0;
	fore (i, 1, sz(s))
		ans += (s[i - 1] == s[i]);
	assert(ans % 2 == 0);
	return ans / 2;
}

inline void solve() {
	int ans = INF;
	fore (k, 0, 2) {
		ans = min(ans, cntSame(string(1, '0' + k) + s + string(1, '1' - k)));
	}
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	while(tc--) {
		assert(read());
		solve();
	}
	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;

void solve(){
	int n;
	scanf("%d", &n);
	vector<int> t(n);
	forn(i, n){
		scanf("%d", &t[i]);
		--t[i];
	}
	sort(t.begin(), t.end());
	vector<vector<int>> dp(n + 1, vector<int>(2 * n, INF));
	dp[0][0] = 0;
	forn(i, n + 1) forn(j, 2 * n - 1) if (dp[i][j] < INF){
		if (i < n) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(t[i] - j));
		dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
	}
	printf("%d\n", dp[n][2 * n - 1]);
}

int main() {
	int q;
	scanf("%d", &q);
	forn(_, q) solve();
}

#include <bits/stdc++.h>

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

using namespace std;

template<typename T>
T hungarian(const vector<vector<T>>& cost) {
    const T INF = numeric_limits<T>::max();
    int n = cost.size(), m = cost[0].size();
    vector<T> u(n + 1), v(m + 1), dist(m + 1);
    vector<int> p(m + 1), way(m + 1), used(m + 1);
    for (int i = 1; i <= n; ++i) {
        p[0] = i;
        int j0 = 0;
        fill(dist.begin(), dist.end(), INF);
        do {
            used[j0] = i;
            int i0 = p[j0], j1 = -1;
            T delta = INF;
            for (int j = 1; j <= m; ++j) if (used[j] != i) {
                T cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
                if (cur < dist[j]) dist[j] = cur, way[j] = j0;
                if (dist[j] < delta) delta = dist[j], j1 = j;
            }
            forn(j, m + 1) {
                if (used[j] == i) u[p[j]] += delta, v[j] -= delta;
                else dist[j] -= delta;
            }
            j0 = j1;
        } while (p[j0] != 0);
        for (int j1; j0; j0 = j1)
            p[j0] = p[j1 = way[j0]];
    }
    
    return -v[0];
}

void solve(){
	int n;
	scanf("%d", &n);
	vector<int> t(n);
	forn(i, n){
		scanf("%d", &t[i]);
		--t[i];
	}
	vector<vector<int>> cost(n, vector<int>(2 * n));
	forn(i, n) forn(j, 2 * n) cost[i][j] = abs(t[i] - j);
	printf("%d\n", hungarian(cost));
}

int main() {
	int q;
	scanf("%d", &q);
	forn(_, q) 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 pair<int, int> pt;

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

int n;
vector<int> a;

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

inline void solve() {
	vector<int> h(n, INF);
	h[0] = 0;
	int lst = 0;
	fore (i, 1, n) {
		if (i - 1 > 0 && a[i - 1] > a[i])
			lst++;
		h[i] = h[lst] + 1;
	}
	cout << h[n - 1] << 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 forn(i, n) for (int i = 0; i < int(n); ++i)

const int N = 500 * 1000 + 13;

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

int main() {
	scanf("%d%d", &n, &k);
	forn(i, n) scanf("%d", &a[i + 1]);
	a[0] = -1e9;
	a[n + 1] = 2e9;
	forn(i, n + 2) a[i] -= i;
	forn(i, k) scanf("%d", &b[i + 1]);
	b[k + 1] = n + 1;
	
	int ans = 0;
	forn(i, k + 1) {
		int l = b[i], r = b[i + 1];
		if (a[l] > a[r]) {
			puts("-1");
			return 0;
		}
		vector<int> lis;
		for (int j = l + 1; j < r; ++j) if (a[l] <= a[j] && a[j] <= a[r]) {
			auto pos = upper_bound(lis.begin(), lis.end(), a[j]);
			if (pos == lis.end()) lis.push_back(a[j]);
			else *pos = a[j];
		}
		ans += (r - l - 1) - int(lis.size());
	}
	
	printf("%d\n", ans);
}

#include<bits/stdc++.h>

using namespace std;

const int N = 5043;
const int MOD = 998244353;

int dp[N][N];
int pdp[N][N];
int cntLess[N];
int lastLess[N];
int a[N];
int n;

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

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

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

int main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	for(int i = 0; i < n; i++)
	{
	 	cntLess[i] = 0;
	 	lastLess[i] = -1;
	 	for(int j = 0; j < n; j++)
	 		if(a[j] * 2 <= a[i])
	 		{
	 		 	lastLess[i] = j;
	 		 	cntLess[i]++;
	 		}
	}
	for(int i = 0; i < n; i++)
	{
	 	dp[i][1] = 1;
	 	pdp[i + 1][1] = add(pdp[i][1], dp[i][1]);
	}
	for(int k = 2; k <= n; k++)
		for(int i = 0; i < n; i++)
		{
			if(cntLess[i] + 1 >= k)
		 		dp[i][k] = add(mul(dp[i][k - 1], add(cntLess[i], sub(2, k))), pdp[lastLess[i] + 1][k - 1]);
		 	else
		 		dp[i][k] = 0;
		 	//cerr << i << " " << k << " " << dp[i][k] << endl;                                
		 	pdp[i + 1][k] = add(pdp[i][k], dp[i][k]);
		}

	cout << dp[n - 1][n] << endl;
}

#include <bits/stdc++.h>

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

using namespace std;

const int AL = 26;

vector<int> val;
vector<int> pos;

struct aho_corasick {
	struct node {
		map<int, int> nxt, go;
		int p, pch;
		int suf, ssuf;
		multiset<int> vals;
		bool term;
		
		node() {
			nxt.clear();
			go.clear();
			suf = ssuf = -1;
			term = false;
			vals.clear();
			p = -1, pch = -1;
		}
	};

	vector<node> nodes;
	
	aho_corasick() {
		nodes = vector<node>(1, node());
	}

	int add(const string& s) {
		int v = 0;
		forn(i, s.size()) {
			int c = s[i] - 'a';
			if (!nodes[v].nxt.count(c)) {
				nodes.push_back(node());
				nodes[v].nxt[c] = int(nodes.size()) - 1;
				nodes.back().p = v;
				nodes.back().pch = c;
			}
			v = nodes[v].nxt[c];
		}
		nodes[v].term = true;
		nodes[v].vals.insert(0);
		return v;
	}
	
	int feed(const string &s){
		int v = 0;
		int ans = -1;
		forn(i, s.size()){
			int c = s[i] - 'a';
			v = go(v, c);
			int u = v;
			while (u != 0){
				if (!nodes[u].vals.empty())
					ans = max(ans, *nodes[u].vals.rbegin());
				u = ssuf(u);
			}
		}
		return ans;
	}
	
	int go(int v, int c) {
		if (nodes[v].go.count(c))
			return nodes[v].go[c];
		if (nodes[v].nxt.count(c))
			return nodes[v].go[c] = nodes[v].nxt[c];
		if (v == 0)
			return nodes[v].go[c] = 0;
		return nodes[v].go[c] = go(suf(v), c);
	}
	
	int suf(int v) {
		if (nodes[v].suf != -1)
			return nodes[v].suf;
		if (v == 0 || nodes[v].p == 0)
			return nodes[v].suf = 0;
		return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
	}
	
	int ssuf(int v) {
		if (nodes[v].ssuf != -1)
			return nodes[v].ssuf;
		if (v == 0 || nodes[v].p == 0)
			return nodes[v].ssuf = 0;
		int s = suf(v);
		if (nodes[s].term)
			return nodes[v].ssuf = s;
		return nodes[v].ssuf = ssuf(s);
	}
};

aho_corasick ac;

int main() {
	int n, m;
	ios::sync_with_stdio(!cin.tie(0));
	cin >> n >> m;
	pos.resize(n);
	val.resize(n, 0);
	
	vector<int> tp2;
	
	ac = aho_corasick();
	
	forn(i, n){
		string s;
		cin >> s;
		pos[i] = ac.add(s);
	}
	
	forn(i, m){
		int t;
		cin >> t;
		if (t == 1){
			int j, x;
			cin >> j >> x;
			--j;
			ac.nodes[pos[j]].vals.erase(ac.nodes[pos[j]].vals.find(val[j]));
			val[j] = x;
			ac.nodes[pos[j]].vals.insert(val[j]);
		}
		else{
			string q;
			cin >> q;
			printf("%d\n", ac.feed(q));
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int AL = 26;
vector<vector<pair<int, int>>> upd;
vector<int> ans;
int n, m;

struct segtree{
	vector<int*> where;
	vector<int> vals;
	vector<int> t;
	int n;
	
	segtree(){}
	
	segtree(int n) : n(n){
		t.assign(4 * n, -1);
		where.clear();
		vals.clear();
	}
	
	void updh(int v, int l, int r, int L, int R, int val){
		if (L >= R)
			return;
		if (l == L && r == R){
			where.push_back(&t[v]);
			vals.push_back(t[v]);
			t[v] = max(t[v], val);
			return;
		}
		int m = (l + r) / 2;
		updh(v * 2, l, m, L, min(m, R), val);
		updh(v * 2 + 1, m, r, max(m, L), R, val);
	}
	
	void upd(int l, int r, int val){
		updh(1, 0, n, l, r, val);
	}
	
	int geth(int v, int l, int r, int pos){
		if (l == r - 1)
			return t[v];
		int m = (l + r) / 2;
		if (pos < m)
			return max(t[v], geth(v * 2, l, m, pos));
		return max(t[v], geth(v * 2 + 1, m, r, pos));
	}
	
	int get(int pos){
		return geth(1, 0, n, pos);
	}
	
	void rollback(){
		*where.back() = vals.back();
		where.pop_back();
		vals.pop_back();
	}
};

segtree st;

struct aho_corasick {
	struct node {
		map<int, int> nxt, go;
		int p, pch;
		int suf, ssuf;
		vector<int> term, qs;
		
		node() {
			nxt.clear();
			go.clear();
			suf = ssuf = -1;
			term.clear();
			p = -1, pch = -1;
			qs.clear();
		}
	};

	vector<node> nodes;
	vector<vector<int>> g;
	
	aho_corasick() {
		nodes = vector<node>(1, node());
	}

	void add(const string& s, int id) {
		int v = 0;
		forn(i, s.size()) {
			int c = s[i] - 'a';
			if (!nodes[v].nxt.count(c)) {
				nodes.push_back(node());
				nodes[v].nxt[c] = int(nodes.size()) - 1;
				nodes.back().p = v;
				nodes.back().pch = c;
			}
			v = nodes[v].nxt[c];
		}
		nodes[v].term.push_back(id);
	}
	
	void feed(const string &s, int id){
		int v = 0;
		forn(i, s.size()){
			int c = s[i] - 'a';
			v = go(v, c);
			nodes[v].qs.push_back(id);
		}
	}
	
	int go(int v, int c) {
		if (nodes[v].go.count(c))
			return nodes[v].go[c];
		if (nodes[v].nxt.count(c))
			return nodes[v].go[c] = nodes[v].nxt[c];
		if (v == 0)
			return nodes[v].go[c] = 0;
		return nodes[v].go[c] = go(suf(v), c);
	}
	
	int suf(int v) {
		if (nodes[v].suf != -1)
			return nodes[v].suf;
		if (v == 0 || nodes[v].p == 0)
			return nodes[v].suf = 0;
		return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
	}
	
	void build_tree() {
		g.resize(nodes.size());
		forn(v, nodes.size()) {
			int u = suf(v);
			if (v != u)
				g[u].push_back(v);
		}
	}
	
	void dfs(int v){
		int cur = st.where.size();
		for (auto i : nodes[v].term){
			int lst = m;
			for (auto it : upd[i]){
				st.upd(it.first, lst, it.second);
				lst = it.first;
			}
			st.upd(0, lst, 0);
		}
		for (auto j : nodes[v].qs){
			ans[j] = max(ans[j], st.get(j));
		}
		for (int u : g[v]){
			dfs(u);
		}
		int nw = st.where.size();
		forn(_, nw - cur){
			st.rollback();
		}
	}
};

aho_corasick ac;

int main() {
	ios::sync_with_stdio(!cin.tie(0));
	cin >> n >> m;
	upd.resize(n);
	ans.resize(m, -1);
	
	vector<int> tp2;
	
	ac = aho_corasick();
	st = segtree(m);
	
	forn(i, n){
		string s;
		cin >> s;
		ac.add(s, i);
	}
	forn(i, m){
		int t;
		cin >> t;
		if (t == 1){
			int j, x;
			cin >> j >> x;
			--j;
			upd[j].push_back(make_pair(i, x));
		}
		else{
			string q;
			cin >> q;
			ac.feed(q, i);
			tp2.push_back(i);
		}
	}
	forn(i, n){
		reverse(upd[i].begin(), upd[i].end());
	}
	
	ac.build_tree();
	ac.dfs(0);
	for (auto it : tp2)
		cout << ans[it] << "\n";
	return 0;
}

for i in range(int(input())):
    x, y, k = map(int, input().split())
    print(((y + 1) * k - 1 + x - 2) // (x - 1) + k)

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c;
    forn(i, n) cin >> a[i];
    forn(i, n) cin >> b[i];
    forn(i, n) if (!b[i])
        c.push_back(a[i]);
    sort(c.rbegin(), c.rend());
    int j = 0;
    forn(i, n) {
        if (b[i]) cout << a[i] << ' ';
        else cout << c[j++] << ' ';
    }
    cout << '\n';
}

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

#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;
        int ans = 0;
        ans += a[0] == 1;
        for (int i = 1; i < n; ++i) {
            if (a[i] == 0) {
                continue;
            }
            int j = i;
            while (j < n && a[j] == 1) {
                ++j;
            }
            ans += (j - i) / 3;
            i = j - 1;
        }
        cout << ans << endl;
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int get(const set<int> &x, const multiset<int> &len) {
    if (len.empty()) return 0;
    return *x.rbegin() - *x.begin() - *len.rbegin();
}

void add(int p, set<int> &x, multiset<int> &len) {
    x.insert(p);
    auto it = x.find(p);
    int prv = -1, nxt = -1;
    if (it != x.begin()) {
        --it;
        len.insert(p - *it);
        prv = *it;
        ++it;
    }
    ++it;
    if (it != x.end()) {
        len.insert(*it - p);
        nxt = *it;
    }
    if (prv != -1 && nxt != -1) {
        len.erase(len.find(nxt - prv));
    }
}

void rem(int p, set<int> &x, multiset<int> &len) {
    auto it = x.find(p);
    int prv = -1, nxt = -1;
    if (it != x.begin()) {
        --it;
        len.erase(len.find(p - *it));
        prv = *it;
        ++it;
    }
    ++it;
    if (it != x.end()) {
        len.erase(len.find(*it - p));
        nxt = *it;
    }
    x.erase(p);
    if (prv != -1 && nxt != -1) {
        len.insert(nxt - prv);
    }
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n, q;
    cin >> n >> q;
    set<int> x;
    multiset<int> len;
    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        add(p, x, len);
    }
    
    cout << get(x, len) << endl;
    for (int i = 0; i < q; ++i) {
        int t, p;
        cin >> t >> p;
        if (t == 0) {
            rem(p, x, len);
        } else {
            add(p, x, len);
        }
        cout << get(x, len) << endl;
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

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

int bp(int a, int n) {
    int res = 1;
    for (; n > 0; n /= 2) {
        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;
int d[N];
long long sd[N];

long long sum (int l, int r) {
    return (sd[r] - sd[l]) % MOD;
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        scanf("%d", d + i);
    sort(d, d + n);
    for (int i = 0; i < n; ++i)
        sd[i + 1] = sd[i] + d[i];
        
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b); // dur, def
        int cnt = (d + n) - lower_bound(d, d + n, b);
        int res = 0;
        if (cnt >= a) {
            res = mul( mul(cnt - a, inv(cnt)), sum(n - cnt, n) );
            res += mul( mul(cnt - a + 1, inv(cnt + 1)), sum(0, n - cnt) );
            res %= MOD;
        }
        printf("%d\n", res);
    }
    
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

int n, m;
li l, r;

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

const int N = int(2e5) + 555;
vector<int> divs[N];

inline void solve() {
    fore(d, 1, N) {
        for(int pos = d; pos < N; pos += d)
            divs[pos].push_back(d);
    }
    
    li lf = m + 1, rg = m;
    vector<int> cnt(m + 1, 0);
    vector<int> id(m + 1, -1);
    set<int> curDivs;
    
    vector< vector<int> > ans(n + 1);
    
    fore(x1, 1, n + 1) {
        li newlf = (l + x1 - 1) / x1;
        li newrg = r / x1;
        assert(newrg - newlf + 1 >= 0);
        
        while (lf > newlf) {
            lf--;
            for (int d : divs[lf]) {
                if (cnt[d] == 0)
                    curDivs.insert(d);
                cnt[d]++;
                id[d] = (int)lf;
            }
        }
        while (rg > newrg) {
            for (int d : divs[rg]) {
                cnt[d]--;
                if (cnt[d] == 0)
                    curDivs.erase(d);
            }
            rg--;
        }
        
        for (int a : divs[x1]) {
            auto it = curDivs.upper_bound(a);
            if (it == curDivs.end())
                continue;
            
            int b = *it;
            if (x1 / a * 1ll * b <= n) {
                int y1 = id[b];
                
                ans[x1] = {x1, y1, x1 / a * b, y1 / b * a};
            }
        }
    }
    
    fore(i, 1, n + 1) {
        if (ans[i].empty())
            cout << -1 << '\n';
        else {
            cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << '\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);
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

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

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

const int N = 60;

typedef array<int, N> num;

num operator ^(const num &a, const num &b){
    num c;
    forn(i, N){
        c[i] = a[i] + b[i];
        if (c[i] >= 3) c[i] -= 3;
    }
    return c;
}

mt19937 rnd(42);

int main(){
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    forn(i, n){
        scanf("%d", &a[i]);
        --a[i];
    }
    
    vector<num> nums(n);
    forn(i, n) forn(j, N) nums[i][j] = rnd() % 3;
    
    vector<vector<int>> pos(n);
    vector<num> pr(1);
    map<num, int> cnt;
    cnt[pr[0]] = 1;
    int cur = 0;
    long long ans = 0;
    forn(i, n){
        pr.push_back(pr.back() ^ nums[a[i]]);
        pos[a[i]].push_back(i);
        if (pos[a[i]].size() >= 4){
            while (cur <= pos[a[i]][int(pos[a[i]].size()) - 4]){
                --cnt[pr[cur]];
                ++cur;
            }
        }
        ans += cnt[pr.back()];
        ++cnt[pr.back()];
    }
    
    printf("%lld\n", ans);
}

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

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

typedef unsigned long long uli;

vector<int> a;
vector<pair<int, int>> t;
vector<int> ps;

pair<int, int> merge(const pair<int, int> &a, const pair<int, int> &b){
    if (a.first != b.first)
        return min(a, b);
    return make_pair(a.first, a.second + b.second);
}

void push(int v){
    if (v * 2 + 1 < int(ps.size())){
        ps[v * 2] += ps[v];
        ps[v * 2 + 1] += ps[v];
    }
    t[v].first += ps[v];
    ps[v] = 0;
}

void build(int v, int l, int r){
    if (l == r - 1){
        t[v] = make_pair(0, 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]);
}

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

int main(){
    int n;
    scanf("%d", &n);
    a.resize(n);
    forn(i, n){
        scanf("%d", &a[i]);
        --a[i];
    }
    t.resize(4 * n);
    ps.resize(4 * n);
    build(1, 0, n);
    vector<vector<int>> pos(n, vector<int>(1, -1));
    long long ans = 0;
    forn(i, n){
        int k = pos[a[i]].size();
        if (k >= 1) upd(1, 0, n, pos[a[i]][k - 1] + 1, i + 1, 1);
        if (k >= 3) upd(1, 0, n, pos[a[i]][k - 3] + 1, pos[a[i]][k - 2] + 1, -1);
        if (k >= 4) upd(1, 0, n, pos[a[i]][k - 4] + 1, pos[a[i]][k - 3] + 1, 1);
        pos[a[i]].push_back(i);
        push(1);
        if (t[1].first == 0) ans += t[1].second - (n - i - 1);
    }
    printf("%lld\n", ans);
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val c = readLine()!!.groupingBy { it }.eachCount().maxBy { it.value }!!.key
        println(c.toString().repeat(n))
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (p, f) = readLine()!!.split(' ').map { it.toInt() }
        var (cntS, cntW) = readLine()!!.split(' ').map { it.toInt() }
        var (s, w) = readLine()!!.split(' ').map { it.toInt() }
        
        if (s > w) {
            s = w.also { w = s }
            cntS = cntW.also { cntW = cntS }
        }

        var ans = 0
        for (s1 in 0..minOf((p / s), cntS)) {
            val w1 = minOf(cntW, (p - s * s1) / w)
            val s2 = minOf(cntS - s1, f / s)
            val w2 = minOf(cntW - w1, (f - s * s2) / w)
            ans = maxOf(ans, s1 + s2 + w1 + w2)
        }
        println(ans)
    }
}

#include <bits/stdc++.h>

using namespace std;

int t;
string s;
int x;

string f(string s) {
    string res = s;
    for (int i = 0; i < s.size(); ++i) {
        if (i - x >= 0 && s[i - x] == '1' || i + x < s.size() && s[i + x] == '1')
            res[i] = '1';
        else
            res[i] = '0';
    }
    return res;
}

int main() {    
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        cin >> s >> x;
        int n = s.size();
 
        string ns = string(n, '1');
        for (int i = 0; i < n; ++i) {
            if (s[i] == '0') {
                if (i - x >= 0) ns[i - x] = '0';
                if (i + x < n) ns[i + x] = '0';
            }
        }
        if (f(ns) == s) cout << ns << endl;
        else cout << -1 << endl;
    }
    return 0;
}

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

        val cntLeft = IntArray(n) { 0 }
        val cntRight = IntArray(n) { 0 }

        var ans = 0L
        for (j in a.indices) {
            cntRight.fill(0)
            for (k in n - 1 downTo j + 1) {
                ans += cntLeft[a[k]] * cntRight[a[j]]
                cntRight[a[k]]++
            }
            cntLeft[a[j]]++
        }
        println(ans)
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(5e3) + 9;

int n;
int a[N];
int dp[N][N];

int calc (int pos, int x) {
    int &res = dp[pos][x];
    if (res != -1) return res;
    
    if (pos == n) return res = 0;
    res = 1 + calc(pos + 1, n);
    res = min(res, calc(pos + 1, pos) + a[pos]);
    if (x != n) {
        if (a[x] >= a[pos])
            res = min(res, calc(pos + 1, pos));
        else {
            res = min(res, calc(pos + 1, pos) + a[pos] - a[x]);
            res = min(res, 1 + calc(pos + 1, x));
        }
    }
    
    return res;
}

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

    memset(dp, -1, sizeof(dp));       
    printf("%d\n", calc(0, n));
    
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int AL = 9;
const int N = 5000;
const int INF = 1e9;

string s;
int x;

struct node{
    int nxt[AL];
    int p;
    char pch;
    int link;
    int go[AL];
    bool term;
    node(){
        memset(nxt, -1, sizeof(nxt));
        memset(go, -1, sizeof(go));
        link = p = -1;
        term = false;
    }
    int& operator [](int x){
        return nxt[x];
    }
};

vector<node> trie;

void add_string(string s){
    int v = 0;
    for (auto it : s){
        int c = it - '1';
        if (trie[v][c] == -1){
            trie.push_back(node());
            trie[trie.size() - 1].p = v;
            trie[trie.size() - 1].pch = c;
            trie[v][c] = trie.size() - 1;
        }
        v = trie[v][c];
    }
    trie[v].term = true;
}

int go(int v, int c);
 
int get_link(int v){
    if (trie[v].link == -1){
        if (v == 0 || trie[v].p == 0)
            trie[v].link = 0;
        else
            trie[v].link = go(get_link(trie[v].p), trie[v].pch);
    }
    return trie[v].link;
}
 
int go(int v, int c) {
    if (trie[v].go[c] == -1){
        if (trie[v][c] != -1)
            trie[v].go[c] = trie[v][c];
        else
            trie[v].go[c] = (v == 0 ? 0 : go(get_link(v), c));
    }
    return trie[v].go[c];
}

string t;

void brute(int i, int sum){
    if (sum == x){
        bool ok = true;
        for (int l = 0; l < int(t.size()); ++l){
            int cur = 0;
            for (int r = l; r < int(t.size()); ++r){
                cur += (t[r] - '0');
                if (x % cur == 0 && cur != x)
                    ok = false;
            }
        }
        if (ok){
            add_string(t);
        }
        return;
    }
    for (int j = 1; j <= min(x - sum, 9); ++j){
        t += '0' + j;
        brute(i + 1, sum + j);
        t.pop_back();
    }
}

int main() {
    cin >> s >> x;
    trie.push_back(node());
    brute(0, 0);
    vector<vector<int>> dp(s.size() + 1, vector<int>(trie.size(), INF));
    dp[0][0] = 0;
    forn(i, s.size()) forn(j, trie.size()) if (dp[i][j] != INF){
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
        int nxt = go(j, s[i] - '1');
        if (!trie[nxt].term)
            dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j]);
    }
    printf("%d\n", *min_element(dp[s.size()].begin(), dp[s.size()].end()));
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;
const int MOD = 998244353;

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

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 rfact[N];

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

int c(int n, int k)
{
    if(n < 0 || n < k || k < 0)
        return 0;
    return mul(fact[n], mul(rfact[k], rfact[n - k]));
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> l(n), r(n), a(m), b(m);
    for(int i = 0; i < n; i++)
        scanf("%d %d", &l[i], &r[i]);
    for(int i = 0; i < m; i++)
        scanf("%d %d", &a[i], &b[i]);
    vector<int> cnt(n + 2);
    for(int i = 0; i < n; i++)
    {
        cnt[l[i]]++;
        cnt[r[i] + 1]--;
    }
    for(int i = 0; i < n + 1; i++)
        cnt[i + 1] += cnt[i];
    prepare_fact();
    vector<vector<int> > p(2 * m + 1, vector<int>(n + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= 2 * m; j++)
            p[j][i] = add(p[j][i - 1], c(cnt[i] - j, i - j));
    int ans = 0;
    for(int mask = 0; mask < (1 << m); mask++)
    {
        int sign = 1;
        set<int> used;
        for(int i = 0; i < m; i++)
            if(mask & (1 << i))
            {
                sign = mul(sign, MOD - 1);
                used.insert(a[i] - 1);
                used.insert(b[i] - 1);
            }
        int L = 1, R = n;
        for(auto x : used)
        {
            L = max(L, l[x]);
            R = min(R, r[x]);
        }
        if(R < L) continue;
        ans = add(ans, mul(sign, add(p[used.size()][R], -p[used.size()][L - 1])));
    }
    printf("%d\n", ans);
}

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    if a[0] + a[1] > a[-1]:
        print(-1)
    else:
        print(1, 2, n)

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

void solve() {
	string s;
	cin >> s;
	vector<int> a;
	forn(i, sz(s)) if (s[i] == '1') {
		int j = i;
		while (j + 1 < sz(s) && s[j + 1] == '1')
			++j;
		a.push_back(j - i + 1);
		i = j;
	}
	sort(a.rbegin(), a.rend());
	int ans = 0;
	for (int i = 0; i < sz(a); i += 2)
		ans += a[i];
	cout << ans << endl;
}

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

for _ in range(int(input())):
    n = int(input())
    a = input()
    d = {0 : 1}
    res, s = 0, 0
    
    for i in range(n):
        s += int(a[i])
        x = s - i - 1
        if x not in d:
            d[x] = 0
        d[x] += 1
        res += d[x] - 1
        
    print(res)

n = [int(x) for x in input().split()]
a = []
for i in range(3):
	a.append([int(x) for x in input().split()])
	a[i].sort(reverse=True)

dp = [[[0 for i in range(n[2] + 1)] for j in range(n[1] + 1)] for k in range(n[0] + 1)]
ans = 0
for i in range(n[0] + 1):
	for j in range(n[1] + 1):
		for k in range(n[2] + 1):
			if i < n[0] and j < n[1]:
				dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + a[0][i] * a[1][j])
			if i < n[0] and k < n[2]:
				dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + a[0][i] * a[2][k])
			if j < n[1] and k < n[2]:
				dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + a[1][j] * a[2][k])
			ans = max(ans, dp[i][j][k])

print(ans)

#include <bits/stdc++.h>

using namespace std;

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

int n;
set <int> sDouble;
long long sum[2];
set <int> s[2];
int cntDouble[2];

// 0: 0 -> 1
// 1: 1 -> 0
void upd(int id) {
    assert(s[id].size() > 0);
    int x = *s[id].rbegin();
    if (id == 1) x = *s[id].begin();
    bool d = sDouble.count(x);
    
    sum[id] -= x, sum[!id] += x;
    s[id].erase(x), s[!id].insert(x);
    cntDouble[id] -= d, cntDouble[!id] += d;
}


int main(){
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int tp, x;
        cin >> tp >> x;// tp = 1 if double
        
        if (x > 0) {
            sum[0] += x;
            s[0].insert(x);
            cntDouble[0] += tp;
            if (tp) sDouble.insert(x);
        } else {
            x = -x;
            int id = 0;
            if (s[1].count(x)) id = 1;
            else assert(s[0].count(x));
            
            sum[id] -= x;
            s[id].erase(x);
            cntDouble[id] -= tp;
            if (tp) { 
                assert(sDouble.count(x));
                sDouble.erase(x);
            }
        }
        
        int sumDouble = cntDouble[0] + cntDouble[1];
        while (s[1].size() < sumDouble) upd(0);
        while (s[1].size() > sumDouble) upd(1);
        while (s[1].size() > 0 && s[0].size() > 0 && *s[0].rbegin() > *s[1].begin()) {
            upd(0);
            upd(1);
        }
        assert(s[1].size() == sumDouble);
        
        long long res = sum[0] + sum[1] * 2;
        if (cntDouble[1] == sumDouble && sumDouble > 0) {
            res -= *s[1].begin();
            if (s[0].size() > 0) res += *s[0].rbegin();
        }
        cout << res << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int n;
string s;
vector <int> p[2][N];
int nxt[2][N];
int ptr[2];
char buf[N];

int main(){
    cin >> n >> s;
    
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] != '0') nxt[0][i] = 1 + nxt[0][i + 1];
        if (s[i] != '1') nxt[1][i] = 1 + nxt[1][i + 1];
    }
    
    for (int b = 0; b <= 1; ++b) {
        int l = 0;
        while (l < n) {
            if (s[l] == char('0' + b)) {
                ++l;
                continue;
            }
            int r = l + 1;
            while (r < n && s[r] != char('0' + b)) ++r;
            for (int len = 1; len <= r - l; ++len)
                p[b][len].push_back(l);
            l = r;
        }
    }

    for (int len = 1; len <= n; ++len) {
        int pos = 0, res = 0;
        ptr[0] = ptr[1] = 0;
        
        while (pos < n) {
            int npos = INF;
            for (int b = 0; b <= 1; ++b) {
                if (nxt[b][pos] >= len) 
                    npos = min(npos, pos + len);
                while (ptr[b] < p[b][len].size() && pos > p[b][len][ ptr[b] ]) 
                    ++ptr[b];
                if (ptr[b] < p[b][len].size()) 
                    npos = min(npos, p[b][len][ ptr[b] ] + len);
            }
            if (npos != INF) 
                ++res;
            pos = npos;
        }
        
        cout << res << ' ';
    }
    cout << endl;
    
    return 0;
}

#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);
const int K = 200043;
const int M = 1000043;

typedef 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];
int used[M];
int dp[M];

int main()
{
    precalc();
    int n, x, y;
    for(int i = 0; i < M; i++)
        dp[i] = -1;
    scanf("%d %d %d", &n, &x, &y);
    vector<int> A(n + 1);
    for(int i = 0; i <= n; i++)
        scanf("%d", &A[i]);
    for(int i = 0; i <= n; i++)
    {
        a[A[i]] = comp(1.0, 0.0);
        b[K - A[i]] = comp(1.0, 0.0);
    }
    int s = 0;
    multiply(a, K + 1, b, K + 1, c, s);
    for(int i = K + 1; i < s; i++)
        if(c[i].x > 0.5)
            used[(i - K + y) * 2] = 1;
    for(int i = 1; i < M; i++)
    {
        if(!used[i]) continue;
        for(int j = i; j < M; j += i)
            dp[j] = max(dp[j], i);
    }
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        int l;
        scanf("%d", &l);
        printf("%d ", dp[l]);
    }
}

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

Для начала, скажем, что математическое ожидание равно среднему значению дохода по всем позициям и равно сумме значений дохода по всем позициям, деленной на $$$n$$$. Поэтому перейдем к минимизации суммы.

Научимся решать для фиксированного $$$k$$$. Возьмем некоторую расстановку и повернем комнаты так, чтобы последняя комната содержала мимика. Тогда у нас стоят $$$cnt_1$$$ обычных сундуков, затем один мимик, $$$cnt_2$$$ обычных сундуков, один мимик, $$$\dots$$$, $$$cnt_k$$$ обычных сундуков, один мимик. Все $$$cnt_i \ge 0$$$ и $$$\sum \limits_{i=1}^{k} cnt_i = n - k$$$.

Взглянем на один из таких интервалов длины $$$cnt_i$$$. Последний сундук на интервале взят из $$$cnt_i$$$ начальных позиций, второй с конца — $$$cnt_i - 1$$$ раз и так далее.

Найдем оптимальный способ выбрать $$$cnt_i$$$. Зафиксируем некоторые значения $$$cnt_i$$$. Взглянем на наименьшее из них и на наибольшее. Пусть их значения будут равны $$$x$$$ и $$$y$$$. Если они отличаются хотя бы на $$$2$$$ ($$$x \le y - 2$$$), то результат всегда можно сделать лучше, если подвинуть один обычный сундук из большего интервала в меньший.

Теперь все значения $$$cnt_i$$$ выставлены. Осталось только присвоить сундуки оптимальным способом. Выпишем объединение всех последовательностей коэффициентов интервалов $$$\bigcup \limits_{i=1}^{n-k} [1, \dots, cnt_i-1, cnt_i]$$$ и отсортируем в неубывающем порядке. Легко показать, что сундуки должны быть отсортированы в невозрастающем порядке (очень стандартная штука, можно доказать опять же показав, что другая расстановка легко может быть улучшена).

Это позволяет нам написать решение за $$$O(n^2)$$$. Отсортируем все сундуки в самом начале, а затем для любого $$$k$$$ домножим значение $$$i$$$-го сундука на $$$\lfloor \frac{i}{k} \rfloor$$$ и сложим результаты.

Наконец, ускорим решение с помощью префиксных сумм. Заметим, что первые $$$k$$$ значений домножаются на $$$0$$$, вторые $$$k$$$ значений — на $$$1$$$ и так далее. Если $$$n$$$ не делится на $$$k$$$, то последний блок имеет длину меньше $$$k$$$. Тогда можно посчитать ответ для любого $$$k$$$ за $$$O(\frac{n}{k})$$$. А это равно $$$O(\sum \limits_{k=1}^{n} \frac{n}{k})$$$ = $$$O(n \log n)$$$.

Асимптотика решения: $$$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)

Рассмотрим два типа остановок: $$$k$$$ горячих и $$$k$$$ холодных кружек и $$$(k + 1)$$$ горячая и $$$k$$$ холодных кружек.

Первый случай тривиален: температура всегда равна $$$\frac{h + c}{2}$$$. Во втором случае температура всегда строго выше, чем $$$\frac{h + c}{2}$$$. Поэтому, если $$$t \le \frac{h + c}{2}$$$, то ответ всегда $$$2$$$.

Покажем, что в противном случае ответ всегда достигается из второго случая:

Температура после $$$(k + 1)$$$ горячей кружки и $$$k$$$ холодных кружек $$$t_k = \frac{(k + 1) \cdot h + k \cdot c}{2k + 1}$$$. Утверждается, что $$$t_0 > t_1 > \dots$$$. Докажем это по индукции.

Также стоит показать, что этот ряд сходится к $$$\frac{h + c}{2}$$$:

Так что это утверждение показывает нам, что для любого $$$t$$$, больше чем $$$\frac{h + c}{2}$$$, ответ всегда достигается из второго случая.

Это позволяет нам найти такое $$$k$$$, что значение $$$t_k$$$ ровно $$$t$$$. Однако, $$$k$$$ не всегда оказывается целым числом. $$$\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}$$$.

Остается только понять, в какую сторону выгоднее округлять $$$k$$$. Кажется, что некоторые реализации с вещественными числами могут не работать из-за погрешностей вычислений. Однако, можно все целиком провести в целых числах.

Перепишем это выражение, чтобы знаменатель был всегда положительным $$$k = \frac{h - t}{2t - h - c}$$$. Теперь округлим это значение вниз и сравним $$$k$$$ и $$$k + 1$$$.

Оптимальное значение достигается при $$$k$$$, если $$$|\frac{k \cdot (h + c) + h}{2k + 1} - t| \le |\frac{(k + 1) \cdot (h + c) + h}{2k + 3} - t|$$$. Так что $$$|(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)$$$. Иначе ответ $$$k + 1$$$.

Оптимальное значение $$$k$$$ можно также найти бинарным поиском, но формулы получаются такие же, и все равно приходится опираться на монотонность. К тому же формулы помогают определить верхнюю границу на ответ.

Асимптотика решения: $$$O(1)$$$ или $$$O(\log h)$$$ на набор входных данных.

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