#include <bits/stdc++.h>

#define wt while(t--)
#define fast ios_base::sync_with_stdio(false)
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define MOD 1000000007
#define EPS 1e-5
#define INF (1<<28)
#define pi 3.141593
typedef unsigned long long int ull;
typedef long long int ll;

using namespace std;

ll arr[2000];
ll n;

int findMin()
{
    int sum = 0;
    for (ll i = 0; i < n; i++)
        sum += arr[i];
    bool dp[n+1][sum+1];
    for (ll i = 0; i <= n; i++)
        dp[i][0] = true;
    for (ll i = 1; i <= sum; i++)
        dp[0][i] = false;
    for (ll i=1; i<=n; i++)
    {
        for (ll j=1; j<=sum; j++)
        {
            dp[i][j] = dp[i-1][j];
            if (arr[i-1] <= j)
                dp[i][j] |= dp[i-1][j-arr[i-1]];
        }
    }
    ll diff = LLONG_MAX;
    for (ll j=sum/2; j>=0; j--)
    {
        if (dp[n][j] == true)
        {
            diff = sum-2*j;
            break;
        }
    }
    return diff;
}

int main()
{
  ll t,x,y,i;
  cin>>t;
  wt
  {
      cin>>n;
      i = 0;
      while(i<n)
      {
          cin>>x>>y;
          arr[i++] = abs(x-y);
      }
      cout<<findMin()<<endl;
  }
  return 0;
}