All Tracks Problem

Witty's New Restaurant
/

Easy-Medium, Easy-Medium

Problem
Editorial
Analytics

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.

SAMPLE INPUT
2
2
2 3
4 5
1
5 7
SAMPLE OUTPUT
0
2
Explanation

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;

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?