# include <stdio.h>
# include <queue>
# include <algorithm>
using namespace std;
struct node
{
	int pos;
	int d;
	int num;
	friend bool operator <(node n1,node n2)
	{
		if(n1.pos==n2.pos)
			return n1.d>n2.d;//仍的距离从小到大
		return n1.pos>n2.pos;//位置从小到大
	}
};
struct node a;
int main()
{
	int t,n,i,num,sum;
	while(~scanf("%d",&t))
	{
		priority_queue<node>q;
		while(t--)
		{
			scanf("%d",&n);
			num=1;
			for(i=0;i<n;i++)
			{
				scanf("%d%d",&a.pos,&a.d);
				q.push(a);
			}
			a=q.top();
			sum=0;
			while(!q.empty())
			{
                  if(num%2)//奇数次遇到仍
				  {
					  a=q.top(); 
					  sum=a.pos+a.d;//扔到的位置
					  a.pos=a.d+a.pos;
					  q.pop();
					  q.push(a);			  
					  num++;
				  }
				  else
				  {
					  a=q.top();
					  q.pop();
					  num++;
				  }
			}
			printf("%d\n",sum);

		}
	}
	return 0;
}

hdu 1896 Stones(优先队列)