阳春三月，青青草原（恩，很工整的对子~~~），懒羊羊上课又打盹了。村长看到了，想着如何才能提高羊羊们学习的积极性。就在这时。。。。。。他的头上，长出了一棵草。“有了！”他说道，“我们来玩个游戏吧！”（很老的点子，但羊羊们都积极地响应拉~~~） 游戏规则是这样的：每轮由老村长给出两个数字，A和B（A，B<=100）,羊羊们需要把这两组数一一配对,使得每组数的和的最大值最小。 即对于Ａ中包含的数字a1,a2,a3……an，Ｂ中包含的数字b1，b2，b3……bn，（ai,bj）为一对（ai,bj有唯一的配对），所有这样的一对数的和中的最大值要尽可能小（第 i 轮只可以在前 i 组数中选取）。

输入的第一行包含一个整数Ｎ (1 ≤ N ≤ 100000), 表示给出数字的轮数。 以下Ｎ行每行包括每轮给出的两个数字Ａ，Ｂ(1 ≤ A, B ≤ 100)。

输出包括Ｎ行，每行对应每轮。每行应包括相应轮数中和中的最大值的最小值。

样例1：
3
2 8
3 1
1 4

样例2：
3
1 1
2 2
3 3

样例1
10
10
9

样例2：
2
3
4