Ibrahim loves to spend time enjoying nature. One day, he was looking at a log and discovered a colony of ants walking along it. All the ants were walking along the log at the same speed of unit per second, however some ants were walking left while others were walking right. When two ants would collide, they both turned around and walked in the direction they came from. Once an ant reached either end of the log, it jumped off the log.
Ibrahim enjoyed watching the ants scurry around, however he wondered how long it would take for all of the ants to jump off the log. Being his only programmer friend, he has asked you to help him solve this problem.
The first line of input provides the number of test cases, . test cases
follow. Each test case begins with one line containing integers .
The next lines each contain an integer , the position of the ant, and
right, the direction the ant is travelling.
Each ant travels at unit per second and jumps off if they are travelling left and reach or if they are travelling right and reach .
Note: No two ants will start at the same position.
For each test case, your program should output an integer: the time it takes for all the ants to jump off the log.
2 3 3 0 right 3 left 2 right 2 5 2 right 4 left
Explanation for Sample
In the second test case, the ants walk for one second before colliding at .
Then, the ant going right turns around and goes left, taking seconds to reach (travelling for seconds in total).
Meanwhile, the ant that was going left turns around and goes right, taking seconds to reach (travelling seconds in total).
This means that it takes seconds for both ants to jump off the log.