Log in
SOLVE
LATER
Witty is planning to start a new restaurant. For this purpose initially he needs to hire Chef and waiter. So he decided to divide the persons in two groups i.e. either Chef or the waiter. Since checking each and every persons quality could become a tedious task, so he decided to divide people in two groups using some ratings. Every time two persons came in front of Witty and he put one of them in the chef category and other one in the waiter category.But this becomes quite confusing for Witty as the rating of both the persons is very close.He is focusing on dividing people into two groups such that difference of total ratings between the chef group and the waiter group becomes minimum as he feels this will lead to quick success of his restaurant.
You being a loyal friend of Witty. Help him minimize the difference between the chef group and the waiter group.
Input
The first line of the input contains an integer T denoting the number of the test cases.
First line of each test case contains a number N denoting the number of pair of persons.Next N lines contains rating of the persons in pairs as x and y.
Output
You have to print the minimum possible absolute difference between the chef group and the waiter group in new line.
Constraints
1 <= T <= 10
1<= N <= 200
0<= x , y <= 1000000
Absolute difference between x and y is less than 100.
case 1: in the first iteration 2 goes to Waiter and 3 goes to Chef. in the second iteration 5 goes to waiter and 4 goes to Chefs. Hence, making the difference 0 from both sides(2+5)-(3+4)=0;
