The town of San Saba is too small for more than one gunslinger. Unfortunately, all of them turned up on the same day, one fine spring morning. As it turned out, love was in the air and they were all trying to woo Alice, the sheriff's daughter. As only one of them could win her love, they decided to do the only gentlemanly thing left to do - they decided to have a Mexican Standoff.

There are multiple rounds in this standoff. In each round, all gunslingers still alive first form a large circle, with each of them facing the centre of the circle. To prevent a fight for position while forming the circle, the men have decided that they will line up in the lexicographic order of their names, and then connect the ends of the line to form the required circle. Once they have taken their positions Alice drops a scarf from her hand, and the moment it hits the ground all the men simultaneously draw out their two guns (one from the left holster and one from the right) and fire both of them. Each man aims the gun from the left holster at the person to his immediate left in the circle and the other gun at the person to his immediate right. Of course, not all gunslingers are equal - they have different reaction times and hence fire their guns at different times. If a man is fired upon before he can fire, he dies and is thus unable to fire his own gun. If two men fire at each other at exactly the same time, they both die. After the round is over, the bodies of the dead men are removed from the circle by those alive, who then head to the next round. If there is only one man left standing after a round, the standoff is over and the lucky survivor gets to marry Alice. If no one survives after a particular round, then Alice remains single of course.

Unfortunately, Alice only likes some of the men. So she decided that before each round, she would remove a single bullet from the gun in either the left or the right holster (but not both) of at most one of the men. Being a little lazy, she wants to know the minimum number of rounds in which she must remove a bullet so that she gets to marry one of the men she likes. If she does not likes anyone, it means that she wants to remain single.

Input

The first line contains T the number of test cases (1 <= T <= 30). The first line of each test case contains N, the number of gunslingers in town (2 <= N <= 60). Each of the next N lines contains the name of the gunslinger (between 1 and 20 lower case letters, each gunslinger will have a unique name), his reaction time in milliseconds (1 <= reaction time <= 1000) and whether Alice likes him or not (Y or N), separated by spaces.

Output

For each test case, a line containing a single integer equal to the minimum number of rounds in which Alice needs to remove a bullet, or -1 if it is impossible for her desire to be fulfilled.

Example

Input:
3
3
good 100 Y
bad 200 N
ugly 100 N
3 
good 100 N
bad 200 N
ugly 100 N
3 
good 100 Y
bad 100 N
ugly 100 N

Output:
1
0 
-1

Explanation
1. Alice likes only Good, so she removes a bullet from the gun which Ugly will use to fire at Good.
Good survives while Bad and Ugly are killed.
2. Alice doesn't like any of them, and she doesn't have to lift a finger to remain single.
3. Alice likes only Good, but all of them are equally fast, so she can't save him and will remain
single in his memory.