Minimum Cash Flow Problem

Consider 'N' friends who have borrowed money from one another. They now wish to settle their debts by giving or taking cash among themselves in a way that minimizes the total cash flow.

Input:

The first line of input contains an integer T representing the number of test cases. For each test case, the first line contains an integer N, the number of friends. The following N lines each contain N space-separated integers, where each element money[i][j] denotes the amount of money the i-th friend has to pay to the j-th friend.

Output:

For each test case, output a single integer representing the minimal cash flow required to settle all debts among friends. Each output should be on a new line.

Example:

Input:
1
3
0 2000 1000
0 0 3000
1000 0 0
Output:
3000

Explanation:

The friends have the following transactions: A owes B $2000, A owes C $1000, B owes C $3000, C owes A $1000. The minimized cash flow would be A paying $2000 to C and B paying $1000 to C, resulting in a total cash flow of $3000.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 100
• 1 <= MONEY[i][j] <= 10^5

Time Limit: 1 second