Minimal Weight Difference

You are given a number of test cases. In each test case, there are n laundry items with given weights. Your task is to partition these items into two loads, denoted as A and B, such that the absolute difference of their total weights, \( |A - B| \), is minimized.

Input Format: The first line contains an integer \( T \), the number of test cases. Each test case begins with an integer \( n \) denoting the number of items, followed by a line containing \( n \) space-separated integers representing the weights.

Output Format: For each test case, output a single integer representing the minimum possible absolute difference between the total weights of the two loads.

Note: Use an optimal approach (e.g., dynamic programming) to solve this partition problem efficiently.

inputFormat

The first line contains an integer \( T \) representing the number of test cases. For each test case, the first line contains an integer \( n \) (the number of laundry items). The second line contains \( n \) space-separated integers denoting the weights of the items.

outputFormat

For each test case, print the minimum absolute difference between the total weights of the two loads on a new line.

## sample

3
3
1 2 3
4
4 7 2 7
5
1 1 1 1 1

0
2
1

</p>