#include <bits/stdc++.h>

using namespace std;

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

int sum(int a) {
    int result = 0;
    while (a > 0) {
        result += a % 10;
        a /= 10;
    }
    return result;
}

int main() {
    int a;
    cin >> a;
    while (sum(a) % 4 != 0) {
        a++;
    }
    cout << a << 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;
	for (int i = 0; i < q; ++i) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		for (int j = 0; j < n; ++j) {
			cin >> a[j];
		}
		int mn = *min_element(a.begin(), a.end());
		int mx = *max_element(a.begin(), a.end());
		if (mx - mn > 2 * k) cout << -1 << endl;
		else cout << mn + k << 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) {
		long long k, n, a, b;
		cin >> k >> n >> a >> b;
		k -= n * a;
		if (k > 0) {
			cout << n << endl;
		} else {
			k = -k;
			++k;
			long long diff = a - b;
			long long turns = (k + diff - 1) / diff;
			if (turns > n) {
				cout << -1 << '\n';
			} else {
				cout << n - turns << '\n';
			}
		}
	}
	
	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 t = 0; t < q; ++t) {
		int n;
		cin >> n;
		vector<int> cnt(n + 1);
		for (int i = 0; i < n; ++i) {
			int x;
			cin >> x;
			++cnt[x];
		}
		sort(cnt.rbegin(), cnt.rend());
		int ans = cnt[0];
		int lst = cnt[0];
		for (int i = 1; i <= n; ++i) {
			if (lst == 0) break;
			if (cnt[i] >= lst) {
				ans += lst - 1;
				lst -= 1;
			} else {
				ans += cnt[i];
				lst = cnt[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, k;
	cin >> n >> k;
	string s;
	cin >> s;
	
	int ans = 0;
	queue<string> q;
	set<string> st;
	q.push(s);
	st.insert(s);
	while (!q.empty() && int(st.size()) < k) {
		string v = q.front();
		q.pop();
		for (int i = 0; i < int(v.size()); ++i) {
			string nv = v;
			nv.erase(i, 1);
			if (!st.count(nv) && int(st.size()) + 1 <= k) {
				q.push(nv);
				st.insert(nv);
				ans += n - nv.size();
			}
		}
	}
	
	if (int(st.size()) < k) cout << -1 << endl;
	else 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 q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		set<int> st;
		for (int j = 0; j < n; ++j) {
			int x;
			cin >> x;
			st.insert(x);
		}
		
		int ans = 0;
		int mx = *st.rbegin();
		if (mx % 2 == 0 && mx % 3 == 0 && mx % 5 == 0) {
			if (st.count(mx / 2) && st.count(mx / 3) && st.count(mx / 5)) {
				ans = max(ans, mx / 2 + mx / 3 + mx / 5);
			}
		}
		
		vector<int> res;
		while (!st.empty() && int(res.size()) < 3) {
			int x = *st.rbegin();
			st.erase(prev(st.end()));
			bool ok = true;
			for (auto it : res) ok &= (it % x != 0);
			if (ok) res.push_back(x);
		}
		
		ans = max(ans, accumulate(res.begin(), res.end(), 0));
		
		cout << ans << endl;
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

void solve()
{
	int n;
	scanf("%d", &n);
	vector<int> cnt(n);
	vector<int> cnt_good(n);
	for(int i = 0; i < n; i++)
	{
		int a, f;
		scanf("%d %d", &a, &f);
		--a;
		cnt[a]++;
		if(f) cnt_good[a]++;
	}
	vector<vector<int> > types(n + 1);
	for(int i = 0; i < n; i++)
		types[cnt[i]].push_back(cnt_good[i]);
	int ans1 = 0;
	int ans2 = 0;
	multiset<int> cur;
	for(int i = n; i > 0; i--)
	{
		for(auto x : types[i]) cur.insert(x);
		if(!cur.empty())
		{
			int z = *cur.rbegin();
			ans1 += i;
			ans2 += min(i, z);
			cur.erase(cur.find(z));
		}
	}
	printf("%d %d\n", ans1, ans2);
}

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

#include <bits/stdc++.h>

using namespace std;

const long long INF64 = 1e12;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	long long k;
	cin >> n >> k;
	--k; // the whole string costs nothing
	string s;
	cin >> s;
	
	vector<vector<int>> lst(n, vector<int>(26, -1));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 26; ++j) {
			if (i > 0) lst[i][j] = lst[i - 1][j];
		}
		lst[i][s[i] - 'a'] = i;
	}
	
	vector<vector<long long>> dp(n + 1, vector<long long>(n + 1));
	for (int i = 0; i < n; ++i) {
		dp[i][1] = 1;
	}
	
	for (int len = 2; len < n; ++len) {
		for (int i = 1; i < n; ++i) {
			for (int j = 0; j < 26; ++j) {
				if (lst[i - 1][j] != -1) {
					dp[i][len] = min(INF64, dp[i][len] + dp[lst[i - 1][j]][len - 1]);
				}
			}
		}
	}
	
	long long ans = 0;
	for (int len = n - 1; len >= 1; --len) {
		long long cnt = 0;
		for (int j = 0; j < 26; ++j) {
			if (lst[n - 1][j] != -1) {
				cnt += dp[lst[n - 1][j]][len];
			}
		}
		if (cnt >= k) {
			ans += k * (n - len);
			k = 0;
			break;
		} else {
			ans += cnt * (n - len);
			k -= cnt;
		}
	}
	
	if (k == 1) {
		ans += n;
		--k;
	}
	
	if (k > 0) cout << -1 << endl;
	else cout << ans << endl;
	
	return 0;
}