Settle Debt

A group of friends went on a trip and sometimes lent each other money. Each transaction among them is represented by the tuple (X, Y, Z) which means person ‘X’ gave person ‘Y’ $Z. Given a list of ‘N’ transactions between a group of friends, return the minimum number of transactions required to settle the debt.

Example:

Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. Assuming   Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transaction can be represented as [[0, 1, 10], [2, 0, 5]].So here the minimum number of transactions to settle the debt is 2.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains one integer ‘N’ where ‘N’ denotes the number of transactions between a group of friends.

Then N lines contain three space-separated integers ‘X’, ‘Y’ and ‘Z’ which denotes person X gave person Y $Z in the form of N x 3 ‘ARR’ matrix where the first column represents lender, the second column represents receiver and the last column represents the money given.

Output format:

For each test case, print a single line containing a single integer denoting the minimum number of transactions required to settle the debt.

The output for each test case will be printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2, or we could also have the persons 0, 2, 6.

Constraints:

1 <= T <= 10
1 <= N <= 9

Where ‘T’ represents the number of test cases, and ‘N’ represents the number of transactions among the friends.

Time Limit: 1 sec.