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

int T;
int N;
int A[1000], B[1000];
// dp[i][x] : i번째에서 A가 x만큼 담당할 때 B가 담당하게 되는 일의 양
int dp[2][111111];

int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

cin >> T;
while (T--) {
	cin >> N;
	int sum = 0;
	for (int i = 0; i < N; ++i) {
		cin >> A[i] >> B[i];
		sum += A[i];
	}

	fill(&dp[0][0], &dp[0][0] + 2 * 111111, INF);
	dp[0][sum] = 0; // 0번 B가 안맡을 때
	dp[0][sum - A[0]] = B[0]; // 0번 B가 맡을 때

	int idx = 0;
	for (int i = 0; i < N - 1; ++i) {
		// 배열 2개만 쓸꺼
		idx = (idx + 1) % 2; // 지금 볼거
		int pre = (idx + 1) % 2; // 전에 본거

		for (int x = 0; x < 111111; ++x) dp[idx][x] = INF;// 초기화
		for (int x = 0; x < 111111; ++x) { // 모든 일
			if (dp[pre][x] != INF) {
				dp[idx][x] = dp[pre][x]; // i+1 B가 맡을 때
				dp[idx][x - A[i + 1]] = min(dp[idx][x - A[i + 1]], dp[pre][x] + B[i + 1]); // i+1 B가 맡을 때
			}
		}
	}

	int ans = INF;
	for (int x = 0; x < 111111; ++x) ans = min(ans, max(x, dp[idx][x]));

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

return 0;
}