There are 2 types of chocolates in Chocoland denoted by A and B.

The cholates are lined up in a queue.You want to satisfy your friends by distributing some number of non-empty contiguous chocolates such that the ratio of number of type A chocolates to number of type B chocolates is same for all the friends.You have to distribute all the chocolates and satisfy maximum number of friends.
Therefore you have to find the maximum number of friends that can be satisfied.

Input Format

The first line of input contains the number of test cases T .
Each test case starts with one line containing an integer N which is the length of the description of a queue.

Each of the following N lines consists of an integer K and one of the characters A or B, meaning that K characters of the given type (A or B) follow next in the queue.

Output Format

For each test case, output a single line containing the maximum number of friends that can be satisfied.

Constraints

$1 \le T \le 50$

$1 \le N \le 10^5$

$1 \le K \le 10^9$

Length of queue $\le 10^9$