There is a famous olympiad, which has more than a hundred participants. The Olympiad consists of two stages: the elimination stage, and the final stage. At least a hundred participants will advance to the final stage. The elimination stage in turn consists of two contests.

A result of the elimination stage is the total score in two contests, but, unfortunately, the jury lost the final standings and has only standings for the first and for the second contest separately. 

In each contest, the participants are ranked by their point score in non-increasing order. When two participants have a tie (earned the same score), they are ranked by their passport number (in accordance with local regulations, all passport numbers are distinct). 

In the first contest, the participant on the 100-th place scored $a$ points. Also, the jury checked all participants from the 1-st to the 100-th place (inclusive) in the first contest and found out that all of them have at least $b$ points in the second contest.

Similarly, for the second contest, the participant on the 100-th place has $c$ points. And the jury checked that all the participants from the 1-st to the 100-th place (inclusive) have at least $d$ points in the first contest.

After two contests, all participants are ranked by their total score in two contests in non-increasing order. When participants have the same total score, tie-breaking with passport numbers is used. The cutoff score to qualify to the final stage is the total score of the participant on the 100-th place.

Given integers $a$, $b$, $c$, $d$, please help the jury determine the smallest possible value of the cutoff score.


-----Input-----

You need to process $t$ test cases.

The first line contains an integer $t$ ($1 \leq t \leq 3025$) — the number of test cases. Then descriptions of $t$ test cases follow.

The first line of each test case contains four integers $a$, $b$, $c$, $d$ ($0 \le a,\,b,\,c,\,d \le 9$; $d \leq a$; $b \leq c$). 

One can show that for any test case satisfying the constraints above, there is at least one olympiad scenario possible.


-----Output-----

For each test case print a single integer — the smallest possible cutoff score in some olympiad scenario satisfying the given information.


-----Example-----
Input
2
1 2 2 1
4 8 9 2

Output
3
12



-----Note-----

For the first test case, consider the following olympiad scenario: there are $101$ participants in the elimination stage, each having $1$ point for the first contest and $2$ points for the second contest. Hence the total score of the participant on the 100-th place is $3$.

For the second test case, consider the following olympiad scenario:   there are $50$ participants with points $5$ and $9$ for the first and second contest respectively;  $50$ participants with points $4$ and $8$ for the first and second contest respectively;  and $50$ participants with points $2$ and $9$ for the first and second contest respectively.  Hence the total point score of the participant on the 100-th place is $12$.

Difficulty: interview

Starter code:

Solutions:
import sys
import math
def II():
	return int(sys.stdin.readline())
 
def LI():
	return list(map(int, sys.stdin.readline().split()))
 
def MI():
	return map(int, sys.stdin.readline().split())
 
def SI():
	return sys.stdin.readline().strip()
t = II()
for q in range(t):
	a,b,c,d = MI()
	print(max(a+b,c+d))

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) ]))
def invr():
    return(list(map(int,input().split())))

n = inp()

for _ in range(n):
    l = inlt()

    a = l[0]
    b = l[1]
    c = l[2]
    d = l[3]

    if(a+b > c+d):
        print(a+b)
    else:
        print(c+d)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


for _ in range(val()):
    a, b, c, d = li()
    print(max(a + b, c + d))

for i in range(int(input())):
    a,b,c,d = map(int,input().split())
    print(max(a+b,c+d))

try:
    for _ in range(int(input())):
        a,b,c,d=map(int,input().split())
        print(max((a+b),(c+d)))

except:
    pass

for t in range(int(input())):
    a,b,c,d = list(map(int, input().split()))
    print(max(a+b,c+d))


for _ in range(int(input())):
    a,b,c,d = map(int,input().split())
    print(max(a+b,c+d))

x = int(input())
for _ in range(x):
    a, b, c, d = map(int, input().split())
    print(max(a + b, c + d))

# map(int, input().split())
def main():
    a, b, c, d = map(int, input().split())
    f = []
    f += [a + b] * 100
    f += [c + d] * 100
    f.sort()
    print(f[100])

rw = int(input())
for wewq in range(rw):
    main()

import sys
input=sys.stdin.readline

T=int(input())
for _ in range(T):
    a,b,c,d=list(map(int,input().split()))
    print(max(a+b,c+d))


t = int(input())
for _ in range(t):
	a, b, c, d = map(int, input().split())
	print(max(a + b, c + d))

t = int(input())

for _ in range(t):
    a, b, c, d = list(map(int,input().split()))
    print(max(a+b, c+d))