#include <bits/stdc++.h>

using namespace std;

int solveSingle(int best, int other1, int other2)
{
	return max(0, max(other1, other2) + 1 - best);
}

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

	while (t--)
	{
		int a, b, c;
		cin >> a >> b >> c;

		cout << solveSingle(a, b, c) << ' ' << solveSingle(b, a, c) << ' ' << solveSingle(c, a, b) << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const string subseqs[] = { "00", "25", "50", "75" };

const int INF = 100;

int solve(string& s, string& t)
{
	int sptr = s.length() - 1;

	int ans = 0;
	while (sptr >= 0 && s[sptr] != t[1])
	{
		sptr--;
		ans++;
	}

	if (sptr < 0) return INF;

	sptr--;

	while (sptr >= 0 && s[sptr] != t[0])
	{
		sptr--;
		ans++;
	}

	return sptr < 0 ? INF : ans;
}

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

	while (t--)
	{
		string n;
		cin >> n;
		
		int ans = INF;
		for (auto e : subseqs)
			ans = min(ans, solve(n, e));

		cout << ans << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

	while (t--)
	{
		int n, k;
		cin >> n >> k;

		vector<int> x(k);
		for (int i = 0; i < k; i++) cin >> x[i];
		sort(x.rbegin(), x.rend());

		int cnt = 0;
		long long sum = 0;

		while (cnt < x.size() && sum + n - x[cnt] < n)
		{
			sum += n - x[cnt++];
		}

		cout << cnt << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

	while (t--)
	{
		int n;
		cin >> n;

		vector<int> a(n);
		for (int i = 0; i < n; i++) cin >> a[i];

		bool inf = true;
		int minval = a[0];

		for (int i = 1; i < n; i++)
		{
			if (a[i] != a[0])
			{
				inf = false;
				break;
			}
			minval = min(minval, a[i]);
		}

		if (inf)
		{
			cout << "-1\n";
			continue;
		}

		sort(a.begin(), a.end());

		int ans = 0;
		for (int i = 0; i < n; i++)
			ans = gcd(ans, a[i] - minval);
		cout << ans << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

set<int> divs(int n) {  
    set<int> d;
    for (int dd = 1; dd * dd <= n; dd++)
        if (n % dd == 0) {
            d.insert(n / dd);
            d.insert(dd);
        }
    return d;
}

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];
        int k = -1;

        forn(i, n) {
            int minv = a[i];
            int same = 0;
            vector<int> d;
            forn(j, n) {
                if (a[j] == minv)
                    same++;
                else if (a[j] > minv)
                    d.push_back(a[j] - minv);
            }
            if (same >= n / 2) {
                k = INT_MAX;
                continue;
            }
            map<int,int> div_counts;
            for (int di: d)
                for (int dd: divs(di))
                    div_counts[dd]++;
            for (auto p: div_counts)
                if (p.second >= n / 2 - same)
                    k = max(k, p.first);
        }

        cout << (k == INT_MAX ? -1 : k) << endl;
    }
}

#include <bits/stdc++.h>

using namespace std;

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

	while (t--)
	{
		int n, k;
		cin >> n >> k;

		vector<vector<int>> g(n, vector<int>());
		vector<int> rem(n, 0);
		vector<int> layer(n, 0);

		for (int i = 1; i < n; i++)
		{
			int x, y;
			cin >> x >> y;
			x--;
			y--;
			g[x].push_back(y);
			g[y].push_back(x);
			rem[x]++;
			rem[y]++;
		}

		queue<int> q;
		for (int i = 0; i < n; i++)
			if (rem[i] == 1)
			{
				q.push(i);
				layer[i] = 1;
			}

		while (!q.empty())
		{
			int u = q.front();
			q.pop();

			for (int v : g[u])
			{
				if (rem[v] != 1)
				{
					rem[v]--;
					if (rem[v] == 1)
					{
						layer[v] = layer[u] + 1;
						q.push(v);
					}
				}
			}
		}

		int ans = 0;
		for (int i = 0; i < n; i++)
			if (layer[i] > k)
				ans++;

		cout << ans << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 64;

bool dp[MAX_N][MAX_N][MAX_N][MAX_N]; // (taken, red, mod A, mod B) -> may be
pair<bool, int> sert[MAX_N][MAX_N][MAX_N][MAX_N]; // the same -> (true (red) | false(black), prev red/black)

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

	while (t--)
	{
		int n, a, b;
		string x;
		cin >> n >> a >> b >> x;

		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				for (int k = 0; k < a; k++)
					for (int l = 0; l < b; l++)
						dp[i][j][k][l] = false;

		dp[0][0][0][0] = true;

		for(int taken = 0; taken < n; taken++)
			for(int red = 0; red <= taken; red++)
				for(int remA = 0; remA < a; remA++)
					for(int remB = 0; remB < b; remB++)
						if (dp[taken][red][remA][remB])
						{
							// red transition
							dp[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = true;
							sert[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = { true, remA };

							// black transition
							dp[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = true;
							sert[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = { false, remB };
						}

		int bestRed = 0;

		for (int red = 1; red < n; red++)
			if (dp[n][red][0][0] && abs(red - (n - red)) < abs(bestRed - (n - bestRed)))
				bestRed = red;

		if (bestRed == 0)
		{
			cout << "-1\n";
		}
		else
		{
			int taken = n;
			int red = bestRed;
			int remA = 0;
			int remB = 0;
			string ans = "";
			
			while (taken > 0)
			{
				auto way = sert[taken][red][remA][remB];
				if (way.first)
				{
					red--;
					remA = way.second;
					ans.push_back('R');
				}
				else
				{
					remB = way.second;
					ans.push_back('B');
				}
				taken--;
			}

			reverse(ans.begin(), ans.end());
			cout << ans << '\n';
		}
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1'000'000;

int psumOdd[MAX_N + 1];
int psumEven[MAX_N + 1];

void solve()
{
	string s;
	int q;
	cin >> s >> q;
	int n = s.length();

	psumOdd[0] = psumEven[0] = 0;
	for (int i = 0; i < n; i++)
	{
		psumOdd[i + 1] = psumOdd[i];
		psumEven[i + 1] = psumEven[i];

		if (s[i] == '[' || s[i] == ']')
		{
			if (i & 1)
				psumOdd[i + 1]++;
			else
				psumEven[i + 1]++;
		}
	}

	while (q--)
	{
		int l, r;
		cin >> l >> r;
		l--;
		int odd = psumOdd[r] - psumOdd[l];
		int even = psumEven[r] - psumEven[l];
		cout << abs(odd - even) << '\n';
	}
}

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

#include <bits/stdc++.h>

using namespace std;

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

	while (t--)
	{
		int k;
		cin >> k;

		for (int i = 1; ; i++)
		{
			if (i % 3 == 0 || i % 10 == 3)
				continue;
			if (--k == 0)
			{
				cout << i << '\n';
				break;
			}
		}
	}
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

	while (t--)
	{
		ll a, b, c;
		cin >> a >> b >> c;

		ll n = 2 * abs(a - b);
		if (a > n || b > n || c > n)
			cout << -1 << '\n';
		else
		{
			ll d = n / 2 + c;
			while (d > n) d -= n;
			cout << d << '\n';
		}
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

	while (t--)
	{
		int k;
		cin >> k;

		int a = 1;
		int x = 1;
		int i = 1;

		while (k >= x + a)
		{
			x += a;
			a += 2;
			i += 1;
		}

		int m = k - x + 1;
		if (m <= i)
			cout << m << ' ' << i << '\n';
		else
			cout << i << ' ' << (i - (m - i)) << '\n';
	}
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll P2LIM = (ll)2e18;

int solve(string s, string t)
{
	int tp = 0;
	int sp = 0;
	int taken = 0;

	while (sp < s.length() && tp < t.length())
	{
		if(s[sp] == t[tp])
		{
			taken++;
			tp++;
		}
		sp++;
	}

	return (int)s.length() - taken + (int)t.length() - taken;
}

vector<string> ts;

int main()
{
	for (ll p2 = 1; p2 <= P2LIM; p2 *= 2)
		ts.push_back(to_string(p2));

	int t;
	cin >> t;

	while (t--)
	{
		string n;
		cin >> n;

		int ans = n.length() + 1;
		for (auto p2 : ts)
			ans = min(ans, solve(n, p2));
		cout << ans << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int cntsrc[26]; // don't forget to memset it but not cnt
int* cnt = cntsrc - 'a'; // so cnt['a'] = cntsrc[0] and so on

pair<string, string> decrypt(string s)
{
	string order;
	reverse(s.begin(), s.end());
	for (auto c : s)
	{
		if (!cnt[c])
			order.push_back(c);
		cnt[c]++;
	}

	int m = order.length();
	int originalLength = 0;
	for (int i = 0; i < m; i++)
		originalLength += cnt[order[i]] / (m - i);

	reverse(order.begin(), order.end());
	return { string(s.rbegin(), s.rbegin() + originalLength), order };
}

string encrypt(pair<string, string> p)
{
	string result = p.first;

	for (auto c : p.second)
	{
		string temp;
		for (auto d : p.first)
			if (d != c)
			{
				temp.push_back(d);
				result.push_back(d);
			}
		p.first = temp;
	}

	return result;
}

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

	while (t--)
	{
		memset(cntsrc, 0, sizeof(cntsrc));
		string s;
		cin >> s;

		auto ans = decrypt(s);
		auto check = encrypt(ans);

		if (check == s)
			cout << ans.first << ' ' << ans.second << '\n';
		else
			cout << "-1\n";
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

string solve1(string n)
{
	string res(n.length(), '9');
	for (char c = '8'; c >= '0'; c--)
	{
		string t(n.length(), c);
		if (t >= n)
			res = t;
	}

	return res;
}

string solve2(string n)
{
	string res = solve1(n);

	for(char a = '0'; a <= '9'; a++)
		for (char b = a + 1; b <= '9'; b++)
		{
			bool n_ok = true;
			for (int i = 0; i < n.length(); i++)
			{
				if (n[i] < b)
				{
					string t = n;
					if (t[i] < a) t[i] = a;
					else t[i] = b;
					for (int j = i + 1; j < n.length(); j++)
						t[j] = a;
					if (res > t)
						res = t;
				}

				if(n[i] != a && n[i] != b)
				{
					n_ok = false;
					break;
				}
			}

			if (n_ok) return n;
		}

	return res;
}

string solve()
{
	string n;
	int k;
	cin >> n >> k;

	if (k == 1) return solve1(n);
	else return solve2(n);
}

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

	while (t--)
		cout << solve() << '\n';

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

string solve()
{
	string n;
	int k;
	cin >> n >> k;

	while (true)
	{
		set<char> s;
		for (auto c : n) s.insert(c);
		if (s.size() <= k) return n;

		s.clear();
		int ptr = 0;
		for (; ; ptr++)
		{
			s.insert(n[ptr]);
			if (s.size() > k)
			{
				while (n[ptr] == '9')
					ptr--;
				n[ptr]++;
				for (int i = ptr + 1; i < n.size(); i++)
					n[i] = '0';
				break;
			}
		}
	}
}

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

	while (t--)
		cout << solve() << '\n';
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

string solveFillingSuffix(string& n, char d, int from)
{
	for (int i = from; i < n.length(); i++)
		n[i] = d;
	return n;
}

void decAt(map<char, int>& d, char c)
{
	if (d.count(c))
	{
		d[c]--;
		if (d[c] == 0) d.erase(c);
	}
}

string solve()
{
	string n;
	int k;
	cin >> n >> k;

	map<char, int> d;
	int pref = 0;

	while (pref < n.length())
	{
		if (d.count(n[pref]))
		{
			d[n[pref++]]++;
			continue;
		}
		if (d.size() == k) break;
		d[n[pref++]]++;
	}

	if (pref == n.length())
		return n;

	while (true)
	{
		if (n[pref] == '9')
		{
			decAt(d, n[--pref]);
			continue;
		}

		if (d.size() < k)
		{
			d[++n[pref]]++;
			return solveFillingSuffix(n, d.size() < k ? '0' : d.begin()->first, pref + 1);
		}

		auto it = d.upper_bound(n[pref]);
		if (it == d.end())
		{
			decAt(d, n[--pref]);
			continue;
		}

		n[pref] = it->first;
		return solveFillingSuffix(n, d.begin()->first, pref + 1);
	}
}

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

	while (t--)
		cout << solve() << '\n';
	
	return 0;
}

for i in range(0, int(input())):
    n = int(input())
    c1 = n // 3;
    c2 = c1;
    if n % 3 == 1:
        c1 += 1
    elif n % 3 == 2:
        c2 += 1
    print(c1, c2)

#include <bits/stdc++.h>

using namespace std;

const int L = 26;
int cnt[L];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		string s;
		cin >> s;
		memset(cnt, 0, sizeof(cnt));
		for (auto c : s) cnt[c - 'a']++;
		int cnt1 = 0;
		int cnt2 = 0;
		for (int i = 0; i < L; i++)
			if (cnt[i] == 1)
				cnt1++;
			else if (cnt[i] > 0)
				cnt2++;
		cout << (cnt2 + cnt1 / 2) << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200 * 1000 + 13;

int ans[MAX_N];
map<int, vector<int>> indices;

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, k;
		cin >> n >> k;
		indices.clear();
		memset(ans, 0, n * sizeof(ans[0]));
		for (int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			if (indices[x].size() < k)
				indices[x].push_back(i);
		}
		int m = 0;
		for (auto e : indices) m += e.second.size();
		m -= m % k;
		int color = 0;
		for (auto e : indices)
			for (auto i : e.second)
			{
				ans[i] = ++color;
				color %= k;
				if (--m == 0) goto _output;
			}
	_output:
		for (int i = 0; i < n; i++)
			cout << ans[i] << ' ';
		cout << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2 * 100 * 1000 + 13;
const int L = 26;

vector<int> balance[L];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 0; i < L; i++)
			balance[i].clear();
		for (int i = 1; i <= n; i++)
		{
			string s;
			cin >> s;
			int initBalance = -(int)s.length();
			for (int j = 0; j < L; j++)
				balance[j].push_back(initBalance);
			for (auto c : s)
				balance[c - 'a'].back() += 2;
		}
		int bestCount = 0;
		int bestLetter = 0;
		for (int i = 0; i < L; i++)
		{
			auto& b = balance[i];
			sort(b.begin(), b.end());
			reverse(b.begin(), b.end());
			if (b[0] <= 0) continue;
			int sumBalance = b[0];
			int j = 1;
			for (; j < n && sumBalance > 0; j++)
				sumBalance += b[j];
			if (sumBalance <= 0) j--;
			if (j > bestCount)
			{
				bestCount = j;
				bestLetter = i;
			}
		}

		cout << bestCount << endl;
	}
	return 0;
}

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

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, m, kh;
		cin >> n >> m >> kh;
		int kv = n * m / 2 - kh;
		if (n & 1)
		{
			kh -= m / 2;
			if (kh < 0)
			{
				cout << "NO\n";
				continue;
			}
		}
		else if (m & 1)
		{
			kv -= n / 2;
			if (kv < 0)
			{
				cout << "NO\n";
				continue;
			}
		}
		if ((kh & 1) || (kv & 1))
		{
			cout << "NO\n";
			continue;
		}
		cout << "YES\n";
	}
	return 0;
}

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

char field[128][128];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, m, kh;
		cin >> n >> m >> kh;
		int kv = n * m / 2 - kh;
		if (n & 1)
		{
			kh -= m / 2;
			if (kh < 0)
			{
				cout << "NO\n";
				continue;
			}

			for (int i = 0; i < m / 2; i++)
				field[n - 1][i * 2] = field[n - 1][i * 2 + 1] = ((i & 1) ? 'x' : 'y');
		}
		else if (m & 1)
		{
			kv -= n / 2;
			if (kv < 0)
			{
				cout << "NO\n";
				continue;
			}

			for (int i = 0; i < n / 2; i++)
				field[i * 2][m - 1] = field[i * 2 + 1][m - 1] = ((i & 1) ? 'x' : 'y');
		}
		if ((kh & 1) || (kv & 1))
		{
			cout << "NO\n";
			continue;
		}
		for(int i = 0; i < n / 2; i++)
			for (int j = 0; j < m / 2; j++)
			{
				if (kh)
				{
					kh -= 2;
					field[2 * i][2 * j] = field[2 * i][2 * j + 1] = (((i + j) & 1) ? 'a' : 'b');
					field[2 * i + 1][2 * j] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd');
				}
				else
				{
					field[2 * i][2 * j] = field[2 * i + 1][2 * j] = (((i + j) & 1) ? 'a' : 'b');
					field[2 * i][2 * j + 1] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd');
				}
			}

		cout << "YES\n";
		for (int i = 0; i < n; i++)
		{
			field[i][m] = 0;
			cout << field[i] << '\n';
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 6000;

int dp[MAX_N][MAX_N];
int a[MAX_N];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, k;
		cin >> n >> k;
		for (int i = 1; i <= n; i++) cin >> a[i];
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= i; j++)
				dp[i][j] = 0;
		for(int i = 0; i < n; i++)
			for (int j = 0; j <= i; j++)
			{
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
				dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + ((a[i + 1] == j + 1) ? 1 : 0));
			}
		int ans = -1;
		for(int i = n; i >= 0; i--)
			if (dp[n][i] >= k)
			{
				ans = n - i;
				break;
			}
		cout << ans << '\n';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 128;

typedef long long ll;
const ll mod = 1000 * 1000 * 1000 + 7;

ll add(ll x, ll y) { return (x + y) % mod; }
ll mul(ll x, ll y) { return x * y % mod; }

vector<int> g[MAX_N];
bool used[MAX_N];
int cnt[MAX_N];
ll dp[MAX_N][MAX_N];

ll rundp(int m, int k)
{
	for (int i = 0; i <= m; i++)
		for (int j = 0; j <= k; j++)
			dp[i][j] = 0;
	dp[0][0] = 1;
	for (int i = 0; i < m; i++)
		for (int j = 0; j <= k; j++)
		{
			dp[i + 1][j] = add(dp[i + 1][j], dp[i][j]);
			dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], cnt[i]));
		}
	return dp[m][k];
}

void solve()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		g[i].clear();
	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		g[--a].push_back(--b);
		g[b].push_back(a);
	}
	if (k == 2)
	{
		cout << n * (n - 1LL) / 2 % mod << '\n';
		return;
	}
	ll ans = 0;
	for (int center = 0; center < n; center++)
	{
		memset(used, 0, n);
		used[center] = true;

		vector<pair<int, int>> layer;
		int m = g[center].size();
		for (int i = 0; i < m; i++)
		{
			int y = g[center][i];
			layer.emplace_back(y, i);
			cnt[i] = 1;
			used[y] = true;
		}
		while (!layer.empty())
		{
			ans = add(ans, rundp(m, k));
			vector<pair<int, int>> newlayer;
			for (auto p : layer)
			{
				cnt[p.second]--;
				for (auto y : g[p.first])
					if (!used[y])
					{
						newlayer.emplace_back(y, p.second);
						used[y] = true;
						cnt[p.second]++;
					}
			}
			layer = newlayer;
		}
	}
	cout << ans << '\n';
}

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