#include <bits/stdc++.h>
using namespace std;
struct hired_t
{
int battles, size;
hired_t( int s ) : battles( 0 ), size( s ) {}
};
struct state_t: vector< hired_t >
{
int cost, encountered, hired;
state_t() : cost( 0 ), encountered( 0 ), hired( 0 ) {}
bool operator < ( const state_t &s ) const
{
if ( cost != s.cost )
return ( cost < s.cost );
if ( encountered != s.encountered )
return ( encountered < s.encountered );
return hired > s.hired;
}
void battle( int t )
{
int u; stack< vector::iterator > erased;
for( auto it = begin(), iu = end(); it != iu; it++, t -= u, hired -= u )
if ( ( it->size -= ( u = min( t, it->size ) ) ) == 0 || ++(it->battles) == 3 )
hired -= it->size, erased.push( it );
while( !erased.empty() )
erase( erased.top() ), erased.pop();
}
void hire( int t )
{
emplace_back( t ), hired += t;
}
} initial_state;
struct states_t: set< state_t >
{
int min_cost, N, next; struct group_t { int size, cost; } g, group[ 20 ];
states_t(): min_cost( INT_MAX )
{
cin >> N, insert( initial_state );
for( int i = 0; i < N; i++ )
cin >> group[ i ].size >> group[ i ].cost;
}
void goal_state( const state_t &present )
{
if ( present.cost >= min_cost )
return;
min_cost = present.cost;
}
void candidate_state( const state_t &present )
{
if ( present.cost < min_cost )
insert( present );
}
void battle( state_t present )
{
if ( present.encountered < N )
present.battle( g.size ), candidate_state( present );
else
goal_state( present );
}
void pass( state_t present )
{
present.cost += g.cost;
if ( present.encountered < N )
candidate_state( present );
else
goal_state( present );
}
void hire( state_t present )
{
present.cost += 2 * g.cost, present.hire( g.size ), candidate_state( present );
}
void iterate()
{
auto it = begin();
if ( it->cost >= min_cost )
{
erase( it ); return;
}
state_t present( *it ); erase( it ), g = group[ present.encountered++ ];
if ( present.hired >= g.size )
battle( present );
pass( present );
if ( present.encountered < N )
hire( present );
}
};
int main()
{
ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
int T; cin >> T;
while( T-- )
{
states_t states;
while( !states.empty() )
states.iterate();
cout << states.min_cost << '\n';
}
}