for i in range(int(input())):
	n = int(input())
	cnto = sum(list(map(lambda x: int(x) % 2, input().split())))
	print('YES' if cnto == 0 or cnto == n else 'NO')

for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	ok = False
	for i in range(n):
		for j in range(i + 2, n):
			if s[i] == s[j]: ok = True
	print('YES' if ok else 'NO')

#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--) {
		string s;
		cin >> s;
		vector<int> pos;
		pos.push_back(0);
		for (int i = 0; i < int(s.size()); ++i) {
			if (s[i] == 'R') pos.push_back(i + 1);
		}
		pos.push_back(s.size() + 1);
		int ans = 0;
		for (int i = 0; i < int(pos.size()) - 1; ++i) {
			ans = max(ans, pos[i + 1] - pos[i]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (auto &it : a) cin >> it;
	for (auto &it : b) cin >> it;
	vector<int> c(n);
	for (int i = 0; i < n; ++i) {
		c[i] = a[i] - b[i];
	}
	sort(c.begin(), c.end());
	
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		if (c[i] <= 0) continue;
		int pos = lower_bound(c.begin(), c.end(), -c[i] + 1) - c.begin();
		ans += i - pos;
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

bool in(int x, int l, int r) {
	return l <= x && x <= r;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, h, l, r;
	cin >> n >> h >> l >> r;
	vector<int> a(n);
	for (auto &it : a) cin >> it;
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MIN));
	dp[0][0] = 0;
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		sum += a[i];
		for (int j = 0; j <= n; ++j) {
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + in((sum - j) % h, l, r));
			if (j < n) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + in((sum - j - 1) % h, l, r));
		}
	}
	
	cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector<int> a;
vector<int> dp;
vector<int> ans;
vector<vector<int>> g;

void dfs(int v, int p = -1) {
	dp[v] = a[v];
	for (auto to : g[v]) {
		if (to == p) continue;
		dfs(to, v);
		dp[v] += max(dp[to], 0);
	}
}

void dfs2(int v, int p = -1) {
	ans[v] = dp[v];
	for (auto to : g[v]) {
		if (to == p) continue;
		dp[v] -= max(0, dp[to]);
		dp[to] += max(0, dp[v]);
		dfs2(to, v);
		dp[to] -= max(0, dp[v]);
		dp[v] += max(0, dp[to]);
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	a = dp = ans = vector<int>(n);
	g = vector<vector<int>>(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (a[i] == 0) a[i] = -1;
	}
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(0);
	dfs2(0);
	for (auto it : ans) cout << it << " ";
	cout << endl;
	
	return 0;
}

#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 a, b;
		cin >> a >> b;
		if (a == b) cout << 0 << endl;
		else cout << 1 + int((a < b) ^ ((b - a) & 1)) << endl;
	}
	
	return 0;
}

#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, m;
		cin >> n >> m;
		vector<int> a(n);
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
		}
		vector<int> p(n);
		for (int i = 0; i < m; ++i) {
			int pos;
			cin >> pos;
			p[pos - 1] = 1;
		}
		while (true) {
			bool ok = false;
			for (int i = 0; i < n; ++i) {
				if (p[i] && a[i] > a[i + 1]) {
					ok = true;
					swap(a[i], a[i + 1]);
				}
			}
			if (!ok) break;
		}
		bool ok = true;
		for (int i = 0; i < n - 1; ++i) {
			ok &= a[i] <= a[i + 1];
		}
		if (ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

#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, m;
		cin >> n >> m;
		vector<int> a(n);
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
		}
		vector<int> p(n);
		for (int i = 0; i < m; ++i) {
			int pos;
			cin >> pos;
			p[pos - 1] = 1;
		}
		for (int i = 0; i < n; ++i) {
			if (p[i] == 0) continue;
			int j = i;
			while (j < n && p[j]) ++j;
			sort(a.begin() + i, a.begin() + j + 1);
			i = j;
		}
		bool ok = true;
		for (int i = 0; i < n - 1; ++i) {
			ok &= a[i] <= a[i + 1];
		}
		if (ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

#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, m;
		string s;
		cin >> n >> m >> s;
		vector<int> pref(n);
		for (int i = 0; i < m; ++i) {
			int p;
			cin >> p;
			++pref[p - 1];
		}
		for (int i = n - 1; i > 0; --i) {
			pref[i - 1] += pref[i];
		}
		vector<int> ans(26);
		for (int i = 0; i < n; ++i) {
			ans[s[i] - 'a'] += pref[i];
			++ans[s[i] - 'a'];
		}
		for (int i = 0; i < 26; ++i) {
			cout << ans[i] << " ";
		}
		cout << endl;
	}
	
	return 0;
}

#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 a, b, c;
		cin >> a >> b >> c;
		int ans = 1e9;
		int A = -1, B = -1, C = -1;
		for (int cA = 1; cA <= 2 * a; ++cA) {
			for (int cB = cA; cB <= 2 * b; cB += cA) {
				for (int i = 0; i < 2; ++i) {
					int cC = cB * (c / cB) + i * cB;
					int res = abs(cA - a) + abs(cB - b) + abs(cC - c);
					if (ans > res) {
						ans = res;
						A = cA;
						B = cB;
						C = cC;
					}
				}
			}
		}
		cout << ans << endl << A << " " << B << " " << C << endl;
	}
	
	return 0;
}

#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, d;
		cin >> n >> d;
		int ld = 0, rd = n * (n - 1) / 2;
		for (int i = 1, cd = 0; i <= n; ++i) {
			if (!(i & (i - 1))) ++cd;
			ld += cd - 1;
		}
		if (!(ld <= d && d <= rd)) {
			cout << "NO" << endl;
			continue;
		}
	
		vector<int> par(n);
		iota(par.begin(), par.end(), -1);
		
		vector<int> cnt(n, 1);
		cnt[n - 1] = 0;
		
		vector<int> bad(n);
		
		vector<int> dep(n);
		iota(dep.begin(), dep.end(), 0);
		
		int cur = n * (n - 1) / 2;
		while (cur > d) {
			int v = -1;
			for (int i = 0; i < n; ++i) {
				if (!bad[i] && cnt[i] == 0 && (v == -1 || dep[v] > dep[i])) {
					v = i;
				}
			}
			assert(v != -1);
			int p = -1;
			for (int i = 0; i < n; ++i) {
				if (cnt[i] < 2 && dep[i] < dep[v] - 1 && (p == -1 || dep[p] < dep[i])) {
					p = i;
				}
			}
			if (p == -1) {
				bad[v] = 1;
				continue;
			}
			assert(dep[v] - dep[p] == 2);
			--cnt[par[v]];
			--dep[v];
			++cnt[p];
			par[v] = p;
			--cur;
		}
	
		cout << "YES" << endl;
		for (int i = 1; i < n; ++i) cout << par[i] + 1 << " ";
		cout << endl;
	}
		
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

long long get(vector<long long> &f, int pos) {
	long long res = 0;
	for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
		res += f[pos];
	return res;
}

void upd(vector<long long> &f, int pos, int val) {
	for (; pos < int(f.size()); pos |= pos + 1) {
		f[pos] += val;
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<pair<int, int>> p(n);
	for (auto &pnt : p) cin >> pnt.first;
	for (auto &pnt : p) cin >> pnt.second;
	sort(p.begin(), p.end());
	
	vector<int> vs;
	for (auto &pnt : p) vs.push_back(pnt.second);
	sort(vs.begin(), vs.end());
	vs.resize(unique(vs.begin(), vs.end()) - vs.begin());
	
	long long ans = 0;
	vector<long long> cnt(vs.size()), xs(vs.size());
	for (auto &pnt : p) {
		int pos = lower_bound(vs.begin(), vs.end(), pnt.second) - vs.begin();
		ans += get(cnt, pos) * 1ll * pnt.first - get(xs, pos);
		upd(cnt, pos, 1);
		upd(xs, pos, pnt.first);
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef
tree<
	pair<int, int>,
	null_type,
	less<pair<int, int>>,
	rb_tree_tag,
	tree_order_statistics_node_update>
ordered_set;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<pair<int, int>> p(n);
	for (auto &pnt : p) cin >> pnt.first;
	for (auto &pnt : p) cin >> pnt.second;
	sort(p.begin(), p.end());
	
	ordered_set s;
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		int cnt = s.order_of_key(make_pair(p[i].second + 1, -1));
		ans += cnt * 1ll * p[i].first;
		s.insert(make_pair(p[i].second, i));
	}
	s.clear();
	for (int i = n - 1; i >= 0; --i) {
		int cnt = int(s.size()) - s.order_of_key(make_pair(p[i].second - 1, n));
		ans -= cnt * 1ll * p[i].first;
		s.insert(make_pair(p[i].second, i));
	}
	
	cout << ans << endl;
	
	return 0;
}

#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;
		int sum = 0;
		bool odd = false, even = false;
		for (int i = 0; i < n; ++i) {
			int x;
			cin >> x;
			sum += x;
			odd |= x % 2 != 0;
			even |= x % 2 == 0;
		}
		if (sum % 2 != 0 || (odd && even)) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

#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 s;
		cin >> s;
		int ans = 0;
		int pw = 1000 * 1000 * 1000;
		while (s > 0) {
			while (s < pw) pw /= 10;
			ans += pw;
			s -= pw - pw / 10;
		}
		cout << ans << endl;
	}
	
	return 0;
}

#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;
		string s;
		cin >> n >> s;
		int l = -1, r = n;
		map<pair<int, int>, int> vis;
		pair<int, int> cur = {0, 0};
		vis[cur] = 0;
		for (int i = 0; i < n; ++i) {
			if (s[i] == 'L') --cur.first;
			if (s[i] == 'R') ++cur.first;
			if (s[i] == 'U') ++cur.second;
			if (s[i] == 'D') --cur.second;
			if (vis.count(cur)) {
				if (i - vis[cur] + 1 < r - l + 1) {
					l = vis[cur];
					r = i;
				}
			}
			vis[cur] = i + 1;
		}
		if (l == -1) {
			cout << -1 << endl;
		} else {
			cout << l + 1 << " " << r + 1 << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, a, b, k;
	cin >> n >> a >> b >> k;
	vector<int> h(n);
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
		h[i] %= a + b;
		if (h[i] == 0) h[i] += a + b;
		h[i] = ((h[i] + a - 1) / a) - 1;
	}
	sort(h.begin(), h.end());
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (k - h[i] < 0) break;
		++ans;
		k -= h[i];
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 222;
const int AL = 26;

bool dp[N][AL][AL];
pair<pair<int, int>, int> p[N][AL][AL];

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	string s;
	cin >> n >> s;
	dp[0][0][0] = 1;
	for (int i = 0; i < n; ++i) {
		int c = s[i] - 'a';
		for (int c1 = 0; c1 < AL; ++c1) {
			for (int c2 = 0; c2 < AL; ++c2) {
				if (!dp[i][c1][c2]) continue;
				if (c >= c1) {
					dp[i + 1][c][c2] = 1;
					p[i + 1][c][c2] = make_pair(make_pair(c1, c2), 0);
				}
				if (c >= c2) {
					dp[i + 1][c1][c] = 1;
					p[i + 1][c1][c] = make_pair(make_pair(c1, c2), 1);	
				}
			}
		}
	}
	
	int x = -1, y = -1;
	for (int c1 = 0; c1 < AL; ++c1) {
		for (int c2 = 0; c2 < AL; ++c2) {
			if (dp[n][c1][c2]) {
				x = c1, y = c2;
			}
		}
	}
	
	if (x == -1) {
		cout << "NO" << endl;
		return 0;
	}
	
	string res;
	for (int i = n; i > 0; --i) {
		int prvx = p[i][x][y].first.first;
		int prvy = p[i][x][y].first.second;
		if (p[i][x][y].second) res += '1';
		else res += '0';
		x = prvx;
		y = prvy;
	}
	
	reverse(res.begin(), res.end());
	cout << "YES" << endl << res << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	string s;
	cin >> n >> s;
	string res;
	char lst0 = 'a', lst1 = 'a';
	for (int i = 0; i < n; ++i) {
		if (s[i] >= lst0) {
			res += '0';
			lst0 = s[i];
		} else if (s[i] >= lst1) {
			res += '1';
			lst1 = s[i];
		} else {
			cout << "NO" << endl;
			return 0;
		}
	}
	
	cout << "YES" << endl << res << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	string s;
	cin >> n >> s;
	
	vector<int> maxdp(26);
	vector<int> dp(n, 1);
	for (int i = 0; i < n; ++i) {
		for (int c = 25; c > s[i] - 'a'; --c) {
			dp[i] = max(dp[i], maxdp[c] + 1);
		}
		maxdp[s[i] - 'a'] =  max(maxdp[s[i] - 'a'], dp[i]);
	}
	
	cout << *max_element(maxdp.begin(), maxdp.end()) << endl;
	for (int i = 0; i < n; ++i) cout << dp[i] << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> val;
vector<vector<pair<int, int>>> g;

void dfs(int v, int pv, int pe, vector<pair<int, int>> &p) {
	p[v] = make_pair(pv, pe);
	for (auto it : g[v]) {
		int to = it.first;
		int idx = it.second;
		if (to == pv) continue;
		dfs(to, v, idx, p);
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n;
	g = vector<vector<pair<int, int>>>(n);
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].push_back(make_pair(v, i));
		g[v].push_back(make_pair(u, i));
	}
	
	vector<vector<pair<int, int>>> p(n, vector<pair<int, int>>(n));
	for (int i = 0; i < n; ++i) {
		dfs(i, -1, -1, p[i]);
	}
	
	val = vector<int>(n - 1, 1000000);

    cin >> m;
	vector<pair<pair<int, int>, int>> q(m);
	for (int i = 0; i < m; ++i) {
		cin >> q[i].first.first >> q[i].first.second >> q[i].second;
		--q[i].first.first;
		--q[i].first.second;
	}
	sort(q.begin(), q.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
		return a.second < b.second;
	});
	
	for (int i = 0; i < m; ++i) {
		int u = q[i].first.first;
		int v = q[i].first.second;
		while (v != u) {
			int pv = p[u][v].first;
			int pe = p[u][v].second;
			val[pe] = q[i].second;
			v = pv;
		}
	}
	
	for (int i = 0; i < m; ++i) {
		int u = q[i].first.first;
		int v = q[i].first.second;
		int mx = 1000000;
		while (v != u) {
			int pv = p[u][v].first;
			int pe = p[u][v].second;
			mx = min(mx, val[pe]);
			v = pv;
		}
		if (mx != q[i].second) {
			cout << -1 << endl;
			return 0;
		}
	}
	
	for (int i = 0; i < n - 1; ++i) {
		cout << val[i] << " ";
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int a[3], n;
		cin >> a[0] >> a[1] >> a[2] >> n;
		sort(a, a + 3);
		n -= 2 * a[2] - a[1] - a[0];
		if (n < 0 || n % 3 != 0) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
		}
	}
	
	return 0;
}

#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;
    
    for (int tt = 0; tt < t; tt++) {
     	int n;
    	cin >> n;
    	vector<pair<int, int>> a(n);
    	for (int i = 0; i < n; ++i) {
    		cin >> a[i].first >> a[i].second;
    	}
    	sort(a.begin(), a.end());
    	pair<int, int> cur = make_pair(0, 0);
    	string ans;
    	bool ok = true;
    	for (int i = 0; i < n; ++i) {
    		int r = a[i].first - cur.first;
    		int u = a[i].second - cur.second;
    		if (r < 0 || u < 0) {
    			cout << "NO" << endl;
    			ok = false;
    			break;
    		}
    		ans += string(r, 'R');
    		ans += string(u, 'U');
    		cur = a[i];
    	}
    	
    	if (ok)
    	    cout << "YES" << endl << ans << endl;
   }

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		set<int> used;
		for (int i = 2; i * i <= n; ++i) {
			if (n % i == 0 && !used.count(i)) {
				used.insert(i);
				n /= i;
				break;
			}
		}
		for (int i = 2; i * i <= n; ++i) {
			if (n % i == 0 && !used.count(i)) {
				used.insert(i);
				n /= i;
				break;
			}
		}
		if (int(used.size()) < 2 || used.count(n) || n == 1) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
			used.insert(n);
			for (auto it : used) cout << it << " ";
			cout << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q, x;
	cin >> q >> x;
	vector<int> mods(x);
	
	set<pair<int, int>> vals;
	for (int i = 0; i < x; ++i) {
		vals.insert(make_pair(mods[i], i));
	}
	
	for (int i = 0; i < q; ++i) {
		int cur;
		cin >> cur;
		cur %= x;
		vals.erase(make_pair(mods[cur], cur));
		++mods[cur];
		vals.insert(make_pair(mods[cur], cur));
		cout << vals.begin()->first * x + vals.begin()->second << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	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];
			--a[i][j];	
		}
	}
	
	long long ans = 0;
	for (int j = 0; j < m; ++j) {
		vector<int> cnt(n);
		for (int i = 0; i < n; ++i) {
			if (a[i][j] % m == j) {
				int pos = a[i][j] / m;
				if (pos < n) {
					++cnt[(i - pos + n) % n];
				}
			}
		}
		int cur = n - cnt[0];
		for (int i = 1; i < n; ++i) {
			cur = min(cur, n - cnt[i] + i);
		}
		ans += cur;
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

vector<int> p;
vector<vector<int>> g;

pair<int, int> dfs(int v, int par = -1, int dist = 0) {
	p[v] = par;
	pair<int, int> res = make_pair(dist, v);
	for (auto to : g[v]) {
		if (to == par) continue;
		res = max(res, dfs(to, v, dist + 1));
	}
	return res;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	p = vector<int>(n);
	g = vector<vector<int>>(n);
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);	
	}
	
	
	pair<int, int> da = dfs(0);
	pair<int, int> db = dfs(da.y);
	vector<int> diam;
	int v = db.y;
	while (v != da.y) {
		diam.push_back(v);
		v = p[v];
	}
	diam.push_back(da.y);
	
	if (int(diam.size()) == n) {
		cout << n - 1 << " " << endl << diam[0] + 1 << " " << diam[1] + 1 << " " << diam.back() + 1 << endl;
	} else {
		queue<int> q;
		vector<int> d(n, -1);
		for (auto v : diam) {
			d[v] = 0;
			q.push(v);
		}
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (auto to : g[v]) {
				if (d[to] == -1) {
					d[to] = d[v] + 1;
					q.push(to);
				}
			}
		}
		pair<int, int> mx = make_pair(d[0], 0);
		for (int v = 1; v < n; ++v) {
			mx = max(mx, make_pair(d[v], v));
		}
		cout << int(diam.size()) - 1 + mx.x << endl << diam[0] + 1 << " " << mx.y + 1 << " " << diam.back() + 1 << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; ++i) {
		int h, m;
		scanf("%d %d", &h, &m);
		printf("%d\n", 1440 - h * 60 - m);
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n, k;
		cin >> n >> k;
		int full = n - n % k;
		full += min(n % k, k / 2);
		cout << full << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> f(n);
	vector<int> in(n), out(n);
	for (int i = 0; i < n; ++i) {
		cin >> f[i];
		--f[i];
		if (f[i] != -1) {
			++out[i];
			++in[f[i]];
		}
	}
	
	vector<int> loops;
	for (int i = 0; i < n; ++i) {
		if (in[i] == 0 && out[i] == 0) {
			loops.push_back(i);
		}
	}
	if (loops.size() == 1) {
		int idx = loops[0];
		for (int i = 0; i < n; ++i) {
			if (in[i] == 0 && i != idx) {
				f[idx] = i;
				++out[idx];
				++in[i];
				break;
			}
		}
	} else if (loops.size() > 1) {
		for (int i = 0; i < int(loops.size()); ++i) {
			int cur = loops[i];
			int nxt = loops[(i + 1) % int(loops.size())];
			f[cur] = nxt;
			++out[cur];
			++in[nxt];
		}
	}
	loops.clear();
	vector<int> ins, outs;
	for (int i = 0; i < n; ++i) {
		if (in[i] == 0) ins.push_back(i);
		if (out[i] == 0) outs.push_back(i);
	}
	assert(ins.size() == outs.size());
	for (int i = 0; i < int(outs.size()); ++i) {
		f[outs[i]] = ins[i];
	}
	
	for (int i = 0; i < n; ++i) {
		cout << f[i] + 1 << " ";
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

mt19937 rnd(time(NULL));

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<int> x(n);
	for (int i = 0; i < n; ++i) {
		cin >> x[i];
	}
	queue<int> q;
	map<int, int> d;
	for (int i = 0; i < n; ++i) {
		d[x[i]] = 0;
		q.push(x[i]);
	}
	long long ans = 0;
	vector<int> res;
	while (!q.empty()) {
		if (int(res.size()) == m) break;
		int cur = q.front();
		q.pop();
		if (d[cur] != 0) {
			ans += d[cur];
			res.push_back(cur);
		}
		if (!d.count(cur - 1)) {
			d[cur - 1] = d[cur] + 1;
			q.push(cur - 1);
		}
		if (!d.count(cur + 1)) {
			d[cur + 1] = d[cur] + 1;
			q.push(cur + 1);
		}
	}
	cout << ans << endl;
	shuffle(res.begin(), res.end(), rnd);
	for (auto it : res) cout << it << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

int n;
vector<int> a, cnt;

int solvemin(){
	int res = 0;
	forn(i, n){
		if (!cnt[i]) continue;
		++res;
		i += 2;
	}
	return res;
}

int solvemax(){
	int res = 0;
	int dist = 2;
	bool right = false;
	forn(i, n){
		if (!cnt[i]){
			++dist;
			continue;
		}
		int j = i - 1;
		int sum = 0;
		while (j + 1 < n && cnt[j + 1]){
			++j;
			sum += cnt[j];
		}
		res += (j - i + 1);
		if (sum > j - i + 1 && (!right || dist > 1)){
			--sum;
			++res;
		}
		right = false;
		if (sum > j - i + 1){
			right = true;
			++res;
		}
		i = j;
		dist = 0;
	}
	return res;
}

int main() {
	scanf("%d", &n);
	a.resize(n);
	cnt.resize(n + 1);
	forn(i, n){
		scanf("%d", &a[i]);
		++cnt[a[i] - 1];
	}
	printf("%d %d\n", solvemin(), solvemax());
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	vector<int> a(n - 1);
	for (int i = 0; i < n - 1; i++)
	{
		scanf("%d", &a[i]);
		a[i]--;
	}
	int root = a[0];
	int last = -1;
	vector<int> used(n, 0);
	printf("%d\n", root + 1);
	int cur = n - 1;
	for (int i = 0; i < n - 1; i++)
	{
		used[a[i]] = 1;
		while (used[cur])
			cur--;
		if (i == n - 2 || used[a[i + 1]])
		{
			printf("%d %d\n", a[i] + 1, cur + 1);
			used[cur] = 1;
		}
		else
			printf("%d %d\n", a[i + 1] + 1, a[i] + 1);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int calc(int a, int b, int c) {
	return abs(a - b) + abs(a - c) + abs(b - c);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		int ans = calc(a, b, c);
		for (int da = -1; da <= 1; ++da) {
			for (int db = -1; db <= 1; ++db) {
				for (int dc = -1; dc <= 1; ++dc) {
					int na = a + da;
					int nb = b + db;
					int nc = c + dc;
					ans = min(ans, calc(na, nb, nc));
				}
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const string MOVES = "LRUD";

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		string s;
		cin >> s;
		map<char, int> cnt;
		for (auto c : MOVES) cnt[c] = 0;
		for (auto c : s) ++cnt[c];
		int v = min(cnt['U'], cnt['D']);
		int h = min(cnt['L'], cnt['R']);
		if (min(v, h) == 0) {
			if (v == 0) {
				h = min(h, 1);
				cout << 2 * h << endl << string(h, 'L') + string(h, 'R') << endl;
			} else {
				v = min(v, 1);
				cout << 2 * v << endl << string(v, 'U') + string(v, 'D') << endl;
			}
		} else {
			string res;
			res += string(h, 'L');
			res += string(v, 'U');
			res += string(h, 'R');
			res += string(v, 'D');
			cout << res.size() << endl << res << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	set<char> st;
	for (int i = 0; i < k; ++i) {
		char c;
		cin >> c;
		st.insert(c);
	}
	
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		int j = i;
		while (j < n && st.count(s[j])) ++j;
		int len = j - i;
		ans += len * 1ll * (len + 1) / 2;
		i = j;
	}
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	int ans = 1;
	
	vector<int> rg(n, 1);
	for (int i = n - 2; i >= 0; --i) {
		if (a[i + 1] > a[i]) rg[i] = rg[i + 1] + 1;
		ans = max(ans, rg[i]);
	}
	
	vector<int> lf(n, 1);
	for (int i = 1; i < n; ++i) {
		if (a[i - 1] < a[i]) lf[i] = lf[i - 1] + 1;
		ans = max(ans, lf[i]);
	}
	
	for (int i = 0; i < n - 2; ++i) {
		if (a[i] < a[i + 2]) ans = max(ans, lf[i] + rg[i + 2]);
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n;
vector<int> a;
vector<int> ans;
vector<vector<int>> g;

void bfs(const vector<int> &start, const vector<int> &end) {
	vector<int> d(n, INF);
	queue<int> q;
	for (auto v : start) {
		d[v] = 0;
		q.push(v);
	}
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto to : g[v]) {
			if (d[to] == INF) {
				d[to] = d[v] + 1;
				q.push(to);
			}
		}
	}
	for (auto v : end) {
		if (d[v] != INF) {
			ans[v] = d[v];
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n;
	a = vector<int>(n);
	g = vector<vector<int>>(n);
	vector<int> even, odd;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (a[i] & 1) odd.push_back(i);
		else even.push_back(i);
	}
	for (int i = 0; i < n; ++i) {
		int lf = i - a[i];
		int rg = i + a[i];
		if (0 <= lf) g[lf].push_back(i);
		if (rg < n) g[rg].push_back(i);
	}
	
	ans = vector<int>(n, -1);
	bfs(odd, even);
	bfs(even, odd);
	for (auto it : ans) cout << it << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int dp[N][N][2 * N];
pair<pair<int, int>, pair<int, char>> p[N][N][2 * N];

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s, t;
	cin >> s >> t;
	int n = s.size(), m = t.size();
	
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= m; ++j) {
			for (int bal = 0; bal < 2 * N; ++bal) {
				dp[i][j][bal] = INF;
			}
		}
	}
	
	dp[0][0][0] = 0;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= m; ++j) {
			for (int bal = 0; bal < 2 * N; ++bal) {
				if (dp[i][j][bal] == INF) continue;
				
				int nxti = i + (i < n && s[i] == '(');
				int nxtj = j + (j < m && t[j] == '(');
				if (bal + 1 < 2 * N && dp[nxti][nxtj][bal + 1] > dp[i][j][bal] + 1) {
					dp[nxti][nxtj][bal + 1] = dp[i][j][bal] + 1;
					p[nxti][nxtj][bal + 1] = make_pair(make_pair(i, j), make_pair(bal, '('));
				}
				
				nxti = i + (i < n && s[i] == ')');
				nxtj = j + (j < m && t[j] == ')');
				if (bal > 0 && dp[nxti][nxtj][bal - 1] > dp[i][j][bal] + 1) {
					dp[nxti][nxtj][bal - 1] = dp[i][j][bal] + 1;
					p[nxti][nxtj][bal - 1] = make_pair(make_pair(i, j), make_pair(bal, ')'));
				}
			}
		}
	}
	
	int ci = n, cj = m, cbal = 0;
	for (int bal = 0; bal < 2 * N; ++bal) {
		if (dp[n][m][bal] + bal < dp[n][m][cbal] + cbal) {
			cbal = bal;
		}
	}
	string res = string(cbal, ')');
	while (ci > 0 || cj > 0 || cbal != 0) {
		int nci = p[ci][cj][cbal].first.first;
		int ncj = p[ci][cj][cbal].first.second;
		int ncbal = p[ci][cj][cbal].second.first;
		res += p[ci][cj][cbal].second.second;
		ci = nci;
		cj = ncj;
		cbal = ncbal;
	}
	reverse(res.begin(), res.end());
	cout << res << endl;
	
	return 0;
}

#include <iostream>

using namespace std;

int main() {
	int q;
	cin >> q;

	for (int qr = 0; qr < q; ++qr) {
		int a, b, n, s;
		cin >> a >> b >> n >> s;

		if (s % n <= b && 1ll * a * n + b >= s) {
			cout << "YES\n";
		}
		else {
			cout << "NO\n";
		}
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (int j = 0; j < n; ++j) {
			cin >> a[j];
			--a[j];
		}
		int pos = 0;
		while (pos < n) {
			int nxt = min_element(a.begin() + pos, a.end()) - a.begin();
			int el = a[nxt];
			a.erase(a.begin() + nxt);
			a.insert(a.begin() + pos, el);
			if (pos == nxt) pos = nxt + 1;
			else pos = nxt;
		}
		for (auto it : a) cout << it + 1 << " ";
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m, d;
	cin >> n >> m >> d;
	vector<int> c(m);
	for (int i = 0; i < m; ++i) {
		cin >> c[i];
	}
	
	vector<int> ans(n + 2);
	for (int i = m - 1, pos = n; i >= 0; --i) {
		for (int len = 0; len < c[i]; ++len) {
			ans[pos - len] = i + 1;
		}
		pos -= c[i];
	}
	
	int now = 0;
	while (true) {
		while (now + 1 < n + 1 && ans[now + 1] > 0) ++now;
		if (now + d >= n + 1) break;
		if (ans[now + d] == 0) {
			int lpos = -1;
			for (int i = now + d; i < n + 2; ++i) {
				if (ans[i] != 0) {
					lpos = i;
					break;
				}
			}
			if (lpos == -1) {
				cout << "NO" << endl;
				return 0;
			}
			int rpos = -1;
			for (int i = lpos; i < n + 2; ++i) {
				if (ans[i] == ans[lpos]) rpos = i;
			}
			while (ans[now + d] == 0) {
				swap(ans[lpos - 1], ans[rpos]);
				--lpos, --rpos;
			}
		}
		now += d;
	}
	
	cout << "YES" << endl;
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << " ";
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	while (q--) {
		int n;
		long long k;
		string s;
		cin >> n >> k >> s;
		string res;
		int cnt = 0;
		bool printed = false;
		for (int i = 0; i < n; ++i) {
			if (s[i] == '0') {
				if (cnt <= k) {
					res += '0';
					k -= cnt;
				} else {
					res += string(cnt - k, '1');
					res += '0';
					res += string(k, '1');
					res += s.substr(i + 1);
					cout << res << endl;
					printed = true;
					break;
				}
			} else {
				++cnt;
			}
		}
	
		if (!printed) {
			res += string(cnt, '1');
			cout << res << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pt;

#define x first
#define y second
#define mp make_pair

const int N = 200043;
const int INF = int(1e9) + 43;

int n;
int dp[N];
int p[N];
pt a[N];
int t[N];

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
    	a[i].y = i;
    	scanf("%d", &a[i].x);
    }
    sort(a, a + n);
    for(int i = 1; i <= n; i++)
    {
    	dp[i] = INF;
    	p[i] = -1;
    }
    for(int i = 0; i < n; i++)
    	for(int j = 3; j <= 5 && i + j <= n; j++)
    	{
    		int diff = a[i + j - 1].x - a[i].x;
    		if(dp[i + j] > dp[i] + diff)
    		{
    			p[i + j] = i;
    			dp[i + j] = dp[i] + diff;
    		}
    	}
    int cur = n;
    int cnt = 0;
    while(cur != 0)
    {
    	for(int i = cur - 1; i >= p[cur]; i--)
    		t[a[i].y] = cnt;
    	cnt++;
    	cur = p[cur]; 
    }
    printf("%d %d\n", dp[n], cnt);
    for(int i = 0; i < n; i++)
    {
    	if(i) printf(" ");
    	printf("%d", t[i] + 1); 
    }
    puts("");
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		string s, t;
		cin >> n >> s >> t;
		vector<int> cnts(26), cntt(26);
		for (int j = 0; j < n; ++j) {
			++cnts[s[j] - 'a'];
			++cntt[t[j] - 'a'];
		}
		bool ok = true;
		bool good = false;
		for (int j = 0; j < 26; ++j) {
			ok &= cnts[j] == cntt[j];
			good |= cnts[j] > 1;
		}
		if (!ok) {
			cout << "NO" << endl;
			continue;
		}
		if (good) {
			cout << "YES" << endl;
			continue;
		}
		int invs = 0, invt = 0;
		for (int l = 0; l < n; ++l) {
			for (int r = 0; r < l; ++r) {
				invs += s[l] > s[r];
				invt += t[l] > t[r];
			}
		}
		ok &= (invs & 1) == (invt & 1);
		if (ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (int j = 0; j < n; ++j) {
			cin >> a[j];
		}
		bool ok = true;
		for (int p1 = 0; p1 < n; ++p1) {
			for (int p2 = 0; p2 < p1; ++p2) {
				ok &= abs(a[p1] - a[p2]) != 1;
			}
		}
		cout << 2 - ok << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		vector<int> p(n);
		for (int j = 0; j < n; ++j) {
			cin >> p[j];
			--p[j];
		}
		for (int j = 0; j < n; ++j) {
			int cnt = 0;
			int k = j;
			do {
				++cnt;
				k = p[k];
			} while (k != j);
			cout << cnt << " ";
		}
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		vector<int> p(n);
		for (int j = 0; j < n; ++j) {
			cin >> p[j];
			--p[j];
		}
		vector<int> used(n);
		vector<int> ans(n);
		for (int j = 0; j < n; ++j) {
			if (!used[j]) {
				vector<int> cur;
				while (!used[j]) {
					cur.push_back(j);
					used[j] = true;
					j = p[j];
				}
				for (auto el : cur) ans[el] = cur.size();
			}
		}
		for (int j = 0; j < n; ++j) cout << ans[j] << " ";
		cout << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		while (true) {
			bool ok = true;
			int cur = n;
			while (cur > 0) {
				if (ok && cur % 3 == 2) ok = false;
				cur /= 3;
			}
			if (ok) break;
			++n;
		}
		cout << n << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const long long INF64 = 1e18;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		long long n;
		cin >> n;
		vector<int> vals;
		int pos2 = -1;
		while (n > 0) {
			vals.push_back(n % 3);
			if (vals.back() == 2) pos2 = int(vals.size()) - 1;
			n /= 3;
		}
		vals.push_back(0);
		if (pos2 != -1) {
			int pos0 = find(vals.begin() + pos2, vals.end(), 0) - vals.begin();
			vals[pos0] = 1;
			for (int i = pos0 - 1; i >= 0; --i) {
				vals[i] = 0;
			}
		}
		long long ans = 0;
		long long pw = 1;
		for (int i = 0; i < int(vals.size()); ++i) {
			ans += pw * vals[i];
			pw *= 3;
		}
		if (vals.back() == 1) ans = pw / 3;
		cout << ans << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 250;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> segs(n);
	vector<int> cnt(N);
	for (int i = 0; i < n; ++i) {
		cin >> segs[i].first >> segs[i].second;
		++cnt[segs[i].first];
		--cnt[segs[i].second + 1];
	}
	
	for (int i = 0; i + 1 < N; ++i) {
		cnt[i + 1] += cnt[i];
	}
	
	vector<int> ans(n);
	for (int i = 0; i < N; ++i) {
		while (cnt[i] > k) {
			int pos = -1;
			for (int p = 0; p < n; ++p) {
				if (!ans[p] && (segs[p].first <= i && i <= segs[p].second) && (pos == -1 || segs[p].second > segs[pos].second)) {
					pos = p;
				}
			}
			assert(pos != -1);
			for (int j = segs[pos].first; j <= segs[pos].second; ++j) {
				--cnt[j];
			}
			ans[pos] = 1;
		}
	}
	
	cout << accumulate(ans.begin(), ans.end(), 0) << endl;
	for (int i = 0; i < n; ++i) {
		if (ans[i]) cout << i + 1 << " ";
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> segs(n);
	vector<int> cnt(N);
	vector<vector<int>> ev(N);
	for (int i = 0; i < n; ++i) {
		cin >> segs[i].first >> segs[i].second;
		++cnt[segs[i].first];
		--cnt[segs[i].second + 1];
		ev[segs[i].first].push_back(i + 1);
		ev[segs[i].second + 1].push_back(-i - 1);
	}
	
	for (int i = 0; i + 1 < N; ++i) {
		cnt[i + 1] += cnt[i];
	}
	
	vector<int> ans(n), sub(N);
	set<pair<int, int>> curSegs;
	int curSub = 0;																																				
	for (int i = 0; i < N; ++i) {
		curSub += sub[i];
		for (auto it : ev[i]) {
			if (it > 0) {
				curSegs.insert(make_pair(segs[it - 1].second, it - 1));
			} else {
				auto iter = curSegs.find(make_pair(segs[-it - 1].second, -it - 1));
				if (iter != curSegs.end()) curSegs.erase(iter);
			}
		}
		while (cnt[i] - curSub > k) {
			assert(!curSegs.empty());
			int pos = curSegs.rbegin()->second;
			curSegs.erase(prev(curSegs.end()));
			++curSub;
			--sub[segs[pos].second + 1];
			ans[pos] = 1;
		}
	}
	
	cout << accumulate(ans.begin(), ans.end(), 0) << endl;
	for (int i = 0; i < n; ++i) {
		if (ans[i]) cout << i + 1 << " ";
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, c;
	cin >> n >> c;
	vector<int> a(n - 1), b(n - 1);
	for (int i = 0; i < n - 1; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n - 1; ++i) {
		cin >> b[i];
	}
	vector<vector<int>> dp(n, vector<int>(2, INF));
	dp[0][0] = 0, dp[0][1] = c;
	for (int i = 0; i < n - 1; ++i) {
		dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + a[i]);
		dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + a[i]);
		dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + b[i]);
		dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + b[i] + c);
	}
	
	for (int i = 0; i < n; ++i) {
		cout << min(dp[i][0], dp[i][1]) << " ";
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 210;

int n, k;
vector<int> a;
vector<vector<int>> g, dp;

void dfs(int v, int p) {
	dp[v][0] = a[v];
	for (auto to : g[v]) {
		if (to != p) dfs(to, v);
	}
	for (int dep = 0; dep < N; ++dep) {
		if (dep == 0) {
			for (auto to : g[v]) {
				if (to == p) continue;
				dp[v][dep] += dp[to][max(0, k - dep - 1)];
			}
		} else {
			for (auto to : g[v]) {
				if (to == p) continue;
				int cur = dp[to][dep - 1];
				for (auto other : g[v]) {
					if (other == p || other == to) continue;
					cur += dp[other][max(dep - 1, k - dep - 1)];
				}
				dp[v][dep] = max(dp[v][dep], cur);
			}
		}
	}
	for (int dep = N - 1; dep > 0; --dep) {
		dp[v][dep - 1] = max(dp[v][dep - 1], dp[v][dep]);
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> k;
	++k;
	a = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	g = vector<vector<int>>(n);
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dp = vector<vector<int>>(n, vector<int>(N));
	dfs(0, -1);
	cout << dp[0][0] << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 200 + 13;
const int INF = 1e9;

int n, k;
int a[N];
vector<int> g[N];
int dp[N][N];
int d[N];
int tmp[N];

void dfs(int v, int p = -1){
	d[v] = 1;
	dp[v][0] = a[v];
	for (auto u : g[v]) if (u != p){
		dfs(u, v);
		int nw = max(d[v], d[u] + 1);
		forn(i, nw)
			tmp[i] = -INF;
		forn(i, d[v]) for (int j = max(0, k - i); j < d[u]; ++j)
			tmp[min(i, j + 1)] = max(tmp[min(i, j + 1)], dp[v][i] + dp[u][j]);
		forn(i, d[u])
			tmp[i + 1] = max(tmp[i + 1], dp[u][i]);
		forn(i, d[v])
			dp[v][i] = max(dp[v][i], tmp[i]);
		for (int i = d[v]; i < nw; ++i)
			dp[v][i] = tmp[i];
		d[v] = nw;
		for (int i = d[v] - 1; i > 0; --i)
			dp[v][i - 1] = max(dp[v][i - 1], dp[v][i]);
	}
}

int main(){
	scanf("%d%d", &n, &k);
	forn(i, n)
		scanf("%d", &a[i]);
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	dfs(0);
	printf("%d\n", dp[0][0]);
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		int sum = 0;
		for (int j = 0; j < n; ++j) {
			int x;
			cin >> x;
			sum += x;
		}
		cout << (sum + n - 1) / n << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<int> ids;
	for (int i = 0; i < n; ++i) {
		int id;
		cin >> id;
		if (find(ids.begin(), ids.end(), id) == ids.end()) {
			if (int(ids.size()) >= k) ids.pop_back();
			ids.insert(ids.begin(), id);
		}
	}
	
	cout << ids.size() << endl;
	for (auto it : ids) cout << it << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	
	queue<int> q;
	set<int> vals;
	for (int i = 0; i < n; ++i) {
		int id;
		cin >> id;
		if (!vals.count(id)) {
			if (int(q.size()) >= k) {
				int cur = q.front();
				q.pop();
				vals.erase(cur);
			}
			vals.insert(id);
			q.push(id);
		}
	}
	
	vector<int> res;
	while (!q.empty()) {
		res.push_back(q.front());
		q.pop();
	}
	reverse(res.begin(), res.end());
	cout << res.size() << endl;
	for (auto it : res) cout << it << " ";
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		string s[2];
		cin >> n >> s[0] >> s[1];
		int row = 0;
		int pos = 0;
		for (pos = 0; pos < n; ++pos) {
			if (s[row][pos] >= '3') {
				if (s[row ^ 1][pos] < '3') {
					break;
				} else {
					row ^= 1;
				}
			}
		}
		if (pos == n && row == 1) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s;
	cin >> s;
	vector<set<int>> poss(26);
	for (int i = 0; i < int(s.size()); ++i) {
		poss[s[i] - 'a'].insert(i);
	}
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int pos;
			char c;
			cin >> pos >> c;
			--pos;
			poss[s[pos] - 'a'].erase(pos);
			s[pos] = c;
			poss[s[pos] - 'a'].insert(pos);
		} else {
			int l, r;
			cin >> l >> r;
			--l, --r;
			int cnt = 0;
			for (int c = 0; c < 26; ++c) {
				auto it = poss[c].lower_bound(l);
				if (it != poss[c].end() && *it <= r) ++cnt;
			}
			cout << cnt << endl;
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<int> a(m);
	for (int i = 0; i < m; ++i) {
		cin >> a[i];
		--a[i];
	}
	
	vector<long long> res(n);
	for (int j = 0; j < m - 1; ++j) {
		res[0] += abs(a[j] - a[j + 1]);
	}
	
	vector<int> cnt(n);
	vector<vector<int>> adj(n);
	for (int i = 0; i < m - 1; ++i) {
		int l = a[i], r = a[i + 1];
		if (l != r) {
			adj[l].push_back(r);
			adj[r].push_back(l);
		}
		if (l > r) swap(l, r);
		if (r - l < 2) continue;
		++cnt[l + 1];
		--cnt[r];
	}
	for (int i = 0; i < n - 1; ++i) {
		cnt[i + 1] += cnt[i];
	}
	
	for (int i = 1; i < n; ++i) {
		res[i] = res[0] - cnt[i];
		for (auto j : adj[i]) {
			res[i] -= abs(i - j);
			res[i] += j + (j < i);
		}
	}
	
	for (int i = 0; i < n; ++i) {
		cout << res[i] << " ";
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s;
	cin >> s;
	
	vector<int> dp(1 << 20);
	for (int i = 0; i < int(s.size()); ++i) {
		vector<bool> used(20);
		int mask = 0;
		for (int j = 0; i + j < int(s.size()); ++j) {
			if (used[s[i + j] - 'a']) break;
			used[s[i + j] - 'a'] = true;
			mask |= 1 << (s[i + j] - 'a');
			dp[mask] = __builtin_popcount(mask);
		}
	}
	
	for (int mask = 0; mask < (1 << 20); ++mask) {
		for (int pos = 0; pos < 20; ++pos) {
			if ((mask >> pos) & 1) {
				dp[mask] = max(dp[mask], dp[mask ^ (1 << pos)]);
			}
		}
	}
	
	int ans = 0;
	for (int mask = 0; mask < (1 << 20); ++mask) {
		if (dp[mask] == __builtin_popcount(mask)) {
			int comp = ~mask & ((1 << 20) - 1);
			ans = max(ans, dp[mask] + dp[comp]);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int tt = clock();
	
	string s;
	cin >> s;
	
	vector<int> dp(1 << 20);
	vector<int> masks;
	for (int i = 0; i < int(s.size()); ++i) {
		vector<bool> used(20);
		int mask = 0;
		for (int j = 0; i + j < int(s.size()); ++j) {
			if (used[s[i + j] - 'a']) break;
			used[s[i + j] - 'a'] = true;
			mask |= 1 << (s[i + j] - 'a');
			masks.push_back(mask);
		}
	}
	sort(masks.begin(), masks.end());
	masks.resize(unique(masks.begin(), masks.end()) - masks.begin());
	sort(masks.begin(), masks.end(), [](int x, int y){
		return __builtin_popcount(x) > __builtin_popcount(y);
	});
	
	int ans = __builtin_popcount(masks[0]);
	for (int i = 0; i < int(masks.size()); ++i) {
		if (clock() - tt > 1900) {
			break;
		}
		for (int j = i + 1; j < int(masks.size()); ++j) {
			if (!(masks[i] & masks[j])) {
				ans = max(ans, __builtin_popcount(masks[i]) + __builtin_popcount(masks[j]));
				break;
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

n, s = int(input()), list(input())
ans = 0
for i in range(0, n, 2):
	if (s[i] == s[i + 1]):
		s[i] = chr(1 - ord(s[i]) + 2 * ord('a'))
		ans += 1
print(ans)
print(''.join(s))

n, a = int(input()), list(map(int, input().split()))
res = []
ans = 0
for i in range(n):
	pos = -1
	for j in range(n):
		if (pos == -1 or a[j] > a[pos]): pos = j
	res.append(pos + 1)
	ans += i * a[pos] + 1
	a[pos] = 0
print(ans)
print(' '.join([str(x) for x in res]))

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

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

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

typedef long long li;
typedef long double ld;

using namespace std;

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

int x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6;

inline void read() {	
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4 >> x5 >> y5 >> x6 >> y6;
    x1 *= 2, y1 *= 2;
    x2 *= 2, y2 *= 2;
    x3 *= 2, y3 *= 2;
    x4 *= 2, y4 *= 2;
    x5 *= 2, y5 *= 2;
    x6 *= 2, y6 *= 2;
}

inline bool ok(int x, int y, int x1, int y1, int x2, int y2) {
	return x < x1 || x2 < x || y < y1 || y2 < y;
}

inline void solve() {
	for (int x = x1; x <= x2; x++) {
		if (ok(x, y1, x3, y3, x4, y4) && ok(x, y1, x5, y5, x6, y6)) {
			cout << "YES" << endl;
			return;
		}
		if (ok(x, y2, x3, y3, x4, y4) && ok(x, y2, x5, y5, x6, y6)) {
			cout << "YES" << endl;
			return;
		}
	}
	for (int y = y1; y <= y2; y++) {
		if (ok(x1, y, x3, y3, x4, y4) && ok(x1, y, x5, y5, x6, y6)) {
			cout << "YES" << endl;
			return;
		}
		if (ok(x2, y, x3, y3, x4, y4) && ok(x2, y, x5, y5, x6, y6)) {
			cout << "YES" << endl;
			return;
		}	
	}
	cout << "NO" << endl;
}

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

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <random>
#include <ctime>
#include <string>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <stack>

using namespace std;

typedef long long li;
typedef unsigned long long uli;
typedef pair<int, int> pii;
typedef long double ld;

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define forn(i, n) for(int i = 0; i < int(n); ++i)
#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
#define forb(i, n) for(int i = int(n) - 1; i >= 0; --i)
#define vi vector<int>
#define x first
#define y second

const int INF = 2e9;
const li INF64 = 1e18;
const int M = 2 * 1000 * 1000;
const int N = 300 * 1000 + 100;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = 3.14159265359;

pair<pii, pii> intersect(pii a, pii b, pii c, pii d) {
	int lf, rg, up, dn;
	lf = max(min(a.x, b.x), min(c.x, d.x));
	rg = min(max(a.x, b.x), max(c.x, d.x));
	up = min(max(a.y, b.y), max(c.y, d.y));
	dn = max(min(a.y, b.y), min(c.y, d.y));

	if (rg <= lf || up <= dn) return { {0, 0}, {0, 0} };

	return { { lf, dn }, { rg, up } };
}

li square(pii a, pii b) {
	return 1ll * abs(a.x - b.x) * abs(a.y - b.y);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	vector<pii> p(6);

	forn(i, 6)
		cin >> p[i].x >> p[i].y;

	pair<pii, pii> wb1 = intersect(p[0], p[1], p[2], p[3]);
	pair<pii, pii> wb2 = intersect(p[0], p[1], p[4], p[5]);
	pair<pii, pii> inter = intersect(wb1.x, wb1.y, wb2.x, wb2.y);

	li swhite = square(p[0], p[1]);
	li swb1 = square(wb1.x, wb1.y);
	li swb2 = square(wb2.x, wb2.y);
	li sinter = square(inter.x, inter.y);

	if (swhite > swb1 + swb2 - sinter) cout << "YES\n";
	else cout << "NO\n";
}

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

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

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

typedef long long li;
typedef long double ld;

using namespace std;

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

const int N = 200 * 1000 + 13;

int n;
int a[N];

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

inline int gcd(int a, int b) {
	while (a != 0 && b != 0) {
		if (a > b) {
			a %= b;
		} else {
			b %= a;
		}
	}
	return max(a, b);
}

inline void solve() {
	int ma = *max_element(a, a + n);
    li sum = 0;
    for (int i = 0; i < n; i++) {
    	sum += a[i];
    }
    int g = ma - a[0];
    for (int i = 1; i < n; i++) {
    	g = gcd(g, ma - a[i]);
    }    
    li ans = (ma * 1ll * n - sum) / g;
    cout << ans << ' ' << g << endl;
}

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

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	
	while (q--) {
		long long k;
		cin >> k;
		--k;
		long long lst = 0;
		long long nxtpw = 1;
		int numlen = 0;
		for (long long i = 1; ; ++i) {
			if (i == nxtpw) {
				++numlen;
				nxtpw *= 10;
			}
			lst += numlen;
			if (k >= lst) {
				k -= lst;
			} else {
				long long nxtpw = 1;
				int numlen = 0;
				for (long long j = 1; j <= i; ++j) {
					if (j == nxtpw) {
						++numlen;
						nxtpw *= 10;
					}
					if (k >= numlen) {
						k -= numlen;
					} else {
						cout << to_string(j)[k] << endl;
						break;
					}
				}
				break;
			}
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

long long get(long long r) {
	return (r + 1) * r / 2;
}

long long sumto(long long r, int need) {
	long long pw = 1;
	long long sum = 0;
	long long add = 0;
	for (int len = 1; ; ++len) {
		if (pw * 10 - 1 < r) {
			long long cnt = pw * 10 - pw;
			if (need) {
				sum += add * cnt + get(cnt) * len;
				add += cnt * len;
			} else {
				sum += cnt * len;
			}
		} else {
			long long cnt = r - pw + 1;
			if (need) {
				sum += add * cnt + get(cnt) * len;
			} else {
				sum += cnt * len;
			}
			break;
		}
		pw *= 10;
	}
	return sum;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int q;
	cin >> q;
	while (q--) {
		long long k;
		cin >> k;
		--k;
		
		long long l = 1	, r = 1e9;
		long long res = -1;
		while (r - l >= 0) {
			long long mid = (l + r) >> 1;
			if (sumto(mid, 1) > k) {
				res = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		k -= sumto(res - 1, 1);
		
		l = 1, r = res;
		long long num = -1;
		while (r - l >= 0) {
			int mid = (l + r) >> 1;
			if (sumto(mid, 0) > k) {
				num = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		
		cout << to_string(num)[k - sumto(num - 1, 0)] << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;

	vector<long long> dp(n + 1);
	multiset<long long> mins, vals;
	mins.insert(0);
	vector<vector<long long>> del(n);
	for (int i = n - 1; i >= 0; --i) {
		dp[i] = i + 1 +  dp[i + 1];
		if (i + k + 2 <= n) mins.erase(mins.find(dp[i + k + 2]));
		for (auto it : del[i]) vals.erase(vals.find(it));
		if (!vals.empty()) dp[i] = min(dp[i], *vals.begin());
		if (s[i] == '1') {
			long long val = (mins.empty() ? 0 : *mins.begin()) + i + 1;
			dp[i] = min(dp[i], val);
			vals.insert(val);
			if (i - k - 1 >= 0) del[i - k - 1].push_back(val);
		}
		mins.insert(dp[i]);
	}
	
	cout << dp[0] << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	int cnto = 0;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		cnto += x & 1;
	}
	
	cout << min(cnto, n - cnto) << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];
        int ans = 0;
        int right_min = INT_MAX;
        for (int i = n -  1; i >= 0; i--) {
            if (a[i] > right_min)
                ans++;
            right_min = min(right_min, a[i]);
        }
        cout << ans << endl;
    }
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int q;
    cin >> q;
    forn(i, q) {
        long long n, m;
        cin >> n >> m;
        n = n / m;
        vector<int> digits(10);
        forn(i, 10)
            digits[i] = ((i + 1) * m) % 10;
        long long sum = 0;
        forn(i, n % 10)
            sum += digits[i];
        cout << sum + n / 10 * accumulate(digits.begin(), digits.end(), 0LL) << endl;
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	vector<int> poss;
	for (int i = 0; i < n; ++i) {
		int x = a[i];
		while (x > 0) {
			poss.push_back(x);
			x /= 2;
		}
	}
	
	int ans = 1e9;
	for (auto res : poss) {
		vector<int> cnt;
		for (int i = 0; i < n; ++i) {
			int x = a[i];
			int cur = 0;
			while (x > res) {
				x /= 2;
				++cur;
			}
			if (x == res) {
				cnt.push_back(cur);
			}
		}
		if (int(cnt.size()) < k) continue;
		sort(cnt.begin(), cnt.end());
		ans = min(ans, accumulate(cnt.begin(), cnt.begin() + k, 0));
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	vector<vector<int>> vals(200 * 1000 + 11);
	for (int i = 0; i < n; ++i) {
		int x = a[i];
		int cur = 0;
		while (x > 0) {
			vals[x].push_back(cur);
			x /= 2;
			++cur;
		}
	}
	
	int ans = 1e9;
	for (int i = 0; i <= 200 * 1000; ++i) {
		sort(vals[i].begin(), vals[i].end());
		if (int(vals[i].size()) < k) continue;
		ans = min(ans, accumulate(vals[i].begin(), vals[i].begin() + k, 0));
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	string s, t;
	cin >> n >> s >> t;
	string abc = "abc";
	vector<string> res;
	do {
		string cur;
		for (int i = 0; i < n; ++i) cur += abc;
		res.push_back(cur);
		res.push_back(string(n, abc[0]) + string(n, abc[1]) + string(n, abc[2]));
	} while (next_permutation(abc.begin(), abc.end()));
	
	for (auto str : res) {
		if (str.find(s) == string::npos && str.find(t) == string::npos) {
			cout << "YES" << endl << str << endl;
			return 0;
		}
	}
	
	assert(false);
	cout << "NO" << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<int> p1(n), p2(n);
	for (int i = 0; i < n; ++i) {
		cin >> p1[i];
		--p1[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> p2[i];
		--p2[i];
	}
	
	set<int> vals1, vals2;
	vector<int> rb;
	for (int i = 0; i < n; ++i) {
		if (vals2.count(p1[i])) {
			vals2.erase(p1[i]);
		} else {
			vals1.insert(p1[i]);
		}
		if (vals1.count(p2[i])) {
			vals1.erase(p2[i]);
		} else {
			vals2.insert(p2[i]);
		}
		if (vals1.empty() && vals2.empty()) {
			rb.push_back(i);
		}
	}
	
	if (int(rb.size()) < k) {
		cout << "NO" << endl;
	} else {
		string s(n, ' ');
		int l = 0;
		for (int it = 0; it < int(rb.size()); ++it) {
			int r = rb[it];
			char c = 'a' + min(it, 25);
			for (int i = l; i <= r; ++i) {
				s[p1[i]] = c;
			}
			l = r + 1;
		}
		cout << "YES" << endl << s << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

vector<int> p, rk;

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

long long res;

long long get(int cnt) {
	return cnt * 1ll * (cnt - 1) / 2;
}

void merge(int u, int v) {
	u = getp(u);
	v = getp(v);
	
	if (rk[u] < rk[v]) swap(u, v);
	
	res -= get(rk[u]);
	res -= get(rk[v]);
	
	rk[u] += rk[v];
	
	res += get(rk[u]);
	
	p[v] = u;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	
	res = 0;
	p = rk = vector<int>(n, 1);
	iota(p.begin(), p.end(), 0);
	
	vector<pair<int, pair<int, int>>> e(n - 1);
	for (int i = 0; i < n - 1; ++i) {
		cin >> e[i].second.first >> e[i].second.second >> e[i].first;
		--e[i].second.first;
		--e[i].second.second;
	}
	
	vector<pair<int, int>> q(m);
	vector<long long> ans(m);
	for (int i = 0; i < m; ++i) {
		cin >> q[i].first;
		q[i].second = i;
	}
	
	sort(e.begin(), e.end());
	sort(q.begin(), q.end());
	
	int pos = 0;
	for (int i = 0; i < m; ++i) {
		while (pos < n - 1 && e[pos].first <= q[i].first) {
			int u = e[pos].second.first;
			int v = e[pos].second.second;
			merge(u, v);
			++pos;
		}
		ans[q[i].second] = res;
	}
	
	for (int i = 0; i < m; ++i) {
		cout << ans[i] << " ";
	}
	cout << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		vector<int> a(n);
		int pos = -1;
		for (int j = 0; j < n; ++j) {
			cin >> a[j];
			if (a[j] == 1) pos = j;
		}
		bool okl = true, okr = true;
		for (int j = 1; j < n; ++j) {
			okl &= (a[(pos - j + n) % n] == j + 1);
			okr &= (a[(pos + j + n) % n] == j + 1);
		}
		if (okl || okr) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		vector<int> a(4 * n);
		for (int j = 0; j < 4 * n; ++j) {
			cin >> a[j];
		}
		sort(a.begin(), a.end());
		int area = a[0] * a.back();
		bool ok = true;
		for (int i = 0; i < n; ++i) {
			int lf = i * 2, rg = 4 * n - (i * 2) - 1;
			if (a[lf] != a[lf + 1] || a[rg] != a[rg - 1] || a[lf] * 1ll * a[rg] != area) {
				ok = false;
			}
		}
		if (ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	long long g = 0;
	for (int i = 0; i < n; ++i) {
		long long x;
		cin >> x;
		g = __gcd(g, x);
	}
	
	int ans = 0;
	for (int i = 1; i * 1ll * i <= g; ++i) {
		if (g % i == 0) {
			++ans;
			if (i != g / i) {
				++ans;
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s, t;
	cin >> s >> t;
	int ans = 0;
	for (int i = 0; i < int(s.size()); ++i) {
		for (int j = i; j < int(s.size()); ++j) {
			int pos = 0;
			for (int p = 0; p < int(s.size()); ++p) {
				if (i <= p && p <= j) continue;
				if (pos < int(t.size()) && t[pos] == s[p]) ++pos;
			}
			if (pos == int(t.size())) ans = max(ans, j - i + 1);
		}
	}
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s, t;
	cin >> s >> t;
	vector<int> rg(t.size());
	
	for (int i = int(t.size()) - 1; i >= 0; --i) {
		int pos = int(s.size()) - 1;
		if (i + 1 < int(t.size())) pos = rg[i + 1] - 1;
		while (s[pos] != t[i]) --pos;
		rg[i] = pos;
	}
	
	int ans = 0;
	int pos = 0;
	for (int i = 0; i < int(s.size()); ++i) {
		int rpos = int(s.size()) - 1;
		if (pos < int(t.size())) rpos = rg[pos] - 1;
		ans = max(ans, rpos - i + 1);
		if (pos < int(t.size()) && t[pos] == s[i]) ++pos;
	}
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.rbegin(), a.rend());
	int lst = a[0] + 2;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int cur = -1;
		for (int dx = 1; dx >= -1; --dx) {
			if (a[i] + dx > 0 && a[i] + dx < lst) {
				cur = a[i] + dx;
				break;
			}
		}
		if (cur == -1) continue;
		++ans;
		lst = cur;
	}
	cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, r;
	cin >> n >> r;
	vector<pair<int, int>> pos, neg;
	for (int i = 0; i < n; ++i) {
		pair<int, int> cur;
		cin >> cur.first >> cur.second;
		if (cur.second >= 0) pos.push_back(cur);
		else {
		    cur.first = max(cur.first, abs(cur.second));
		    neg.push_back(cur);
		}
	}
	
	sort(pos.begin(), pos.end());
	sort(neg.begin(), neg.end(), comp);
	
	int taken = 0;
	for (int i = 0; i < int(pos.size()); ++i) {
		if (r >= pos[i].first) {
			r += pos[i].second;
			++taken;
		}
	}
	
	vector<vector<int>> dp(neg.size() + 1, vector<int>(r + 1, 0));
	dp[0][r] = taken;
	for (int i = 0; i < int(neg.size()); ++i) {
		for (int cr = 0; cr <= r; ++cr) {
			if (cr >= neg[i].first && cr + neg[i].second >= 0) {
				dp[i + 1][cr + neg[i].second] = max(dp[i + 1][cr + neg[i].second], dp[i][cr] + 1);
			}
			dp[i + 1][cr] = max(dp[i + 1][cr], dp[i][cr]);
		}
	}
	
	int ans = 0;
	for (int cr = 0; cr <= r; ++cr) ans = max(ans, dp[int(neg.size())][cr]);
	cout << (ans == n ? "YES" : "NO") << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, r;
	cin >> n >> r;
	vector<pair<int, int>> pos, neg;
	for (int i = 0; i < n; ++i) {
		pair<int, int> cur;
		cin >> cur.first >> cur.second;
		if (cur.second >= 0) pos.push_back(cur);
		else {
		    cur.first = max(cur.first, abs(cur.second));
		    neg.push_back(cur);
		}
	}
	
	sort(pos.begin(), pos.end());
	sort(neg.begin(), neg.end(), comp);
	
	int taken = 0;
	for (int i = 0; i < int(pos.size()); ++i) {
		if (r >= pos[i].first) {
			r += pos[i].second;
			++taken;
		}
	}
	
	vector<vector<int>> dp(neg.size() + 1, vector<int>(r + 1, 0));
	dp[0][r] = taken;
	for (int i = 0; i < int(neg.size()); ++i) {
		for (int cr = 0; cr <= r; ++cr) {
			if (cr >= neg[i].first && cr + neg[i].second >= 0) {
				dp[i + 1][cr + neg[i].second] = max(dp[i + 1][cr + neg[i].second], dp[i][cr] + 1);
			}
			dp[i + 1][cr] = max(dp[i + 1][cr], dp[i][cr]);
		}
	}
	
	int ans = 0;
	for (int cr = 0; cr <= r; ++cr) ans = max(ans, dp[int(neg.size())][cr]);
	cout << ans << endl;
	
	return 0;
}