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 number of transactions to be made by the friends to tally the expenses.

Input

The first line consists of an integer t, the number of test cases. 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.

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

Output:
1
0
1

Explanation of Test Cases

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: that A can spend for B at many places.