Mirko and Slavko are playing a new game. Again. Slavko starts each round by giving Mirko two numbers $A$ and $B$, both smaller than $100$. Mirko then has to solve the following task for Slavko: how to pair all given $A$ numbers with all given $B$ numbers so that the maximal sum of such pairs is as small as possible.

In other words, if during previous rounds Slavko gave numbers $a_1,a_2,\dots ,a_n$ and $b_1,b_2,\dots ,b_n$, determine $n$ pairings $(a_i,b_j)$ such that each number in $A$ sequence is used in exactly one pairing, and each number in $B$ sequence is used in exactly one pairing and the maximum of all sums $a_i+b_j$ is minimal.

Input Specification

The first line of input contains a single integer $N$ $(1\le N\le {10}^5)$, number of rounds. The next $N$ lines contain two integers $A$ and $B$ $(1\le A,B\le 100)$, numbers given by Slavko in that round.

Output Specification

The output consists of $N$ lines, one for each round. Each line should contain the smallest maximal sum for that round.

Sample Input 1

3
2 8
3 1
1 4

Sample Output 1

10
10
9

Sample Input 2

3
1 1
2 2
3 3

Sample Output 2

2
3
4