include
include
include
using namespace std;
pair arr[225];
int TOT,dp[225][56500];
int solve(int n){
dp[0][0]=true;
for(int i=1;i<56500;i++){
dp[0][i]=false;
}
for(int i=1;i<=n;i++){
for(int j=0;j<56500;j++){
dp[i][j]=false;
if(arr[i-1].first<=j){
dp[i][j] |= dp[i-1][j-arr[i-1].first];
}
if(arr[i-1].second<=j){
dp[i][j] |= dp[i-1][j-arr[i-1].second];
}
}
}
int minn = INT_MAX;
for (int j=56500; j>=0; j--){
if (dp[n][j]){
minn = min(minn,abs(TOT-2*j));
}
}
return minn;
}
int main(){
int tc,n,total;
scanf("%d",&tc);
while(tc--){
scanf("%d",&n);
total=0;
for(int i=0;i<n;i++){
scanf("%d%d",&arr[i].first,&arr[i].second);
total+=arr[i].first+arr[i].second;
}
TOT=total;
printf("%d\n",solve(n));
}
return 0;}