#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';
    }
}