皇后有 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 位大臣颁发奖金，其中第 位大臣所获得的奖金数目为第 位大臣所获得奖金数目与前 位大臣左手上的数的和的较大值再加上第 位大臣右手上的数。 形式化地讲：我们设第 位大臣左手上的正整数为 ，右手上的正整数为 ，则第 位大臣获得的奖金数目为 可以表达为： 当然，吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。 注意：重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

输入描述:

第一行输入整数 ——测试组数。对于每组数据：• 第一行输入整数 ——大臣人数；• 接下来 行，每行输入两个整数 。

输出描述:

对每组数据输出一行，表示在最优站位下，奖金最多的大臣所能获得的最小金币数。