#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>pi; typedef complex<double>cx;
#define int ll
#define X first
#define Y second
#define fer(i,a,n) for(int i=a;i<=n;i++)
#define ref(i,n,a) for(int i=n;i>=a;i--)
#define endl '\n'
#define mem(a,x) memset(a,x,sizeof a)
#define ac IO;int t;cin>>t;while(t--)solve()
#define AC signed main(){IO;solve();}
#define NO {cout<<"No"<<endl;return;}
#define YES {cout<<"Yes"<<endl;return;}
#define re(a) {cout<<a<<endl;return;}
#define all(v) v.begin(),v.end()
//ofstream fout("1.out", ios::out);
//ifstream fin("1.in", ios::in);
//#define cout fout
//#define cin fin
//--------------------瑞神神中神--------------------

const int N=2e5+10,M=18;
int root[N],ans[N];
int n,idx;

struct node
{
    int x,y,id;
}g[N];

bool cmp(node a,node b)
{
    if(a.x^b.x)return a.x<b.x;
    return a.y<b.y;
}

bool cmp1(node a,node b)
{
    if(a.y^b.y)return a.y<b.y;
    return a.x<b.x;
}

struct seg
{
    int l,r,cnt,sum;
}tr[N*4+N*M];

int build(int l,int r)
{
    int p=++idx;
    if(l==r)return p;
    int mid=l+r>>1;
    tr[p].l=build(l,mid);
    tr[p].r=build(mid+1,r);
    return p;
}

int insert(int p,int l,int r,int pos,int x)
{
    int q=++idx;
    tr[q]=tr[p];
    if(l==r)
    {
        tr[q].cnt++;
        tr[q].sum+=x;
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid)tr[q].l=insert(tr[p].l,l,mid,pos,x);
    else tr[q].r=insert(tr[q].r,mid+1,r,pos,x);
    tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;
    tr[q].sum=tr[tr[q].l].sum+tr[tr[q].r].sum;
    return q;
}

int query(int q,int l,int r,int k)
{
    if(l==r)
    {
        return tr[q].sum;
    }
    int cnt=tr[tr[q].l].cnt;
    int mid=l+r>>1;
    if(k<=cnt)
    {
        return query(tr[q].l,l,mid,k);
    }
    else
    {
        return tr[tr[q].l].sum+query(tr[q].r,mid+1,r,k-cnt);
    }
}

int W(int k,int x)
{
    return query(root[x],1,n,k);
}

void calc(int l,int r,int L,int R)
{
    if(l>r)return;
    int mid=l+r>>1;
    int res=1e18,pos=0;
    for(int i=max(L,mid);i<=R;i++)
    {
        int tmp=W(mid,i-1)+g[i].y+g[i].x;
        if(tmp<res)
        {
            res=tmp;pos=i;
        }
    }
    ans[mid]=res;
    calc(l,mid-1,L,pos);
    calc(mid+1,r,pos,R);
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>g[i].x>>g[i].y;
    }
    sort(g+1,g+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        g[i].id=i;
    }
    sort(g+1,g+n+1,cmp1);
    root[0]=build(1,n);
    for(int i=1;i<=n;i++)
    {
        auto[x,y,id]=g[i];
        root[i]=insert(root[i-1],1,n,id,x);
    }
    calc(1,n,1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<'\n';
    }
}

AC