Minimums and Maximums solution codeforces

Minimums and Maximums solution codeforces

An array isÂ beautifulÂ if both of the following two conditions meet:

• there areÂ at leastÂ đť‘™1l1Â andÂ at mostÂ đť‘ź1r1Â elements in the array equal to its minimum;
• there areÂ at leastÂ đť‘™2l2Â andÂ at mostÂ đť‘ź2r2Â elements in the array equal to its maximum.
• [1,1,1,1][1,1,1,1], it hasÂ 44Â minimums andÂ 44Â maximums;
• [4,4,4,4,4][4,4,4,4,4], it hasÂ 55Â minimums andÂ 55Â maximums;
• [1,2,1,2,2,1,2,2,2,2,2,2,2][1,2,1,2,2,1,2,2,2,2,2,2,2], it hasÂ 33Â minimums andÂ 1010Â maximums;
• [8,8,8][8,8,8], it hasÂ 33Â minimums andÂ 33Â maximums;
• [4,6,6][4,6,6], it hasÂ 11Â minimum andÂ 22Â maximums;
• [3,4,3][3,4,3], it hasÂ 22Â minimums andÂ 11Â maximum;
• [5,5,5,5,5,5][5,5,5,5,5,5], it hasÂ 66Â minimums andÂ 66Â maximums.

Minimums and Maximums solution codeforces

For example, the arrayÂ [2,3,2,4,4,3,2][2,3,2,4,4,3,2]Â hasÂ 33Â elements equal to its minimum (11-st,Â 33-rd andÂ 77-th) andÂ 22Â elements equal to its maximum (44-th andÂ 55-th).

Another example: the arrayÂ [42,42,42][42,42,42]Â hasÂ 33Â elements equal to its minimum andÂ 33Â elements equal to its maximum.

Your task is to calculate theÂ minimumÂ possible number of elements in aÂ beautifulÂ array.

Input

The first line contains one integerÂ đť‘ˇtÂ (1â‰¤đť‘ˇâ‰¤50001â‰¤tâ‰¤5000)Â â€” the number of test cases.

Each test case consists of one line containing four integersÂ đť‘™1l1,Â đť‘ź1r1,Â đť‘™2l2Â andÂ đť‘ź2r2Â (1â‰¤đť‘™1â‰¤đť‘ź1â‰¤501â‰¤l1â‰¤r1â‰¤50;Â 1â‰¤đť‘™2â‰¤đť‘ź2â‰¤501â‰¤l2â‰¤r2â‰¤50).

Minimums and Maximums solution codeforces

For each test case, print one integerÂ â€” the minimum possible number of elements in a beautiful array.

Example

input

Copy
7
3 5 4 6
5 8 5 5
3 3 10 12
1 5 3 3
1 1 2 2
2 2 1 1
6 6 6 6


Minimums and Maximums solution codeforces

output

Copy
4
5
13
3
3
3
6


Minimums and Maximums solution codeforces

Optimal arrays in the test cases of the example:

1. [1,1,1,1][1,1,1,1], it hasÂ 44Â minimums andÂ 44Â maximums;
2. [4,4,4,4,4][4,4,4,4,4], it hasÂ 55Â minimums andÂ 55Â maximums;
3. [1,2,1,2,2,1,2,2,2,2,2,2,2][1,2,1,2,2,1,2,2,2,2,2,2,2], it hasÂ 33Â minimums andÂ 1010Â maximums;
4. [8,8,8][8,8,8], it hasÂ 33Â minimums andÂ 33Â maximums;
5. [4,6,6][4,6,6], it hasÂ 11Â minimum andÂ 22Â maximums;
6. [3,4,3][3,4,3], it hasÂ 22Â minimums andÂ 11Â maximum;
7. [5,5,5,5,5,5][5,5,5,5,5,5], it hasÂ 66Â minimums andÂ 66Â maximums.