Problem Statement:

N witty friends went for an outing trip. During the outing they have spent lot of money in lot of places. In some places, a friend (A) spends ‘M’ money for his friend (B).

An expense is described by  "A spends M$ for B"

A transaction is described by “X gives K$ to Y”

You are given all the expenses made by the friends. The outing trip is ended and now you have to find the minimum transactions to be made by the friends to tally the expenses.

 

Input:

The first line consists of an integer t, the number of testcases. For each test case, the first line consists of an integer N, the number of expenses made by friends followed by N lines. Each line contains two strings A and B (A!=B) and an integer m, the money A spent for B.

 

Output:

For each test case, print the minimum number of transactions required to tally the expenses.

 

Input Constraints:

1<=t<=10000

1<=N<=10

A!=B

Each character in A is either 'A' or 'B'

Each character in B is either 'A' or 'B'

1<= length of A,B <=2

1<=m<=10000

 

Sample Input:

 

3

1

AA BB 10

3

A BB 100

BB AA 100

AA A 100

4

AB BA 100

BA B 100

AB B 100

B A 200

 

Sample Output:

1

0

1

Explanation of Testcases:

Case 1: AA spent 10$ for BB. So one transaction "BB gives 10$ to AA" is needed to tally the expense.

Case 2: A spent 100$ for BB, BB spent 100$ for AA and AA spent 100$ for A. In this case, no transactions are required as the expenses are already tallied.

Note: Note that A can spend for B at many places.