Description

LCS has an aircraft, he can use some specific commands to make his aircraft to move. To simple the problem, you can assume the aircraft just move on the 2D-Plane.

There are four commands :fd x, bk x, lt y, rt y.

The command fd causes the aircraft to move forward by the specified number x of meters.

The command bk causes the aircraft to move backward by the specified number x of meters.

The command lt causes the aircraft to turn left by the specified number y of degrees.

The command rt causes the aircraft to turn right by the specified number y of degrees.

After executing many commands, LCS's aircraft maybe far away from it's start position. Your task is to calculate the straight-line distance from the LCS's aircraft present position to the position it started from.

Input

The first line of input contains one integer specifying the number of test cases to follow. Each test case starts with a line containing one integer, the number of commands to follow. The commands follow, one on each line. Each test case will contain no more than 1000 commands.

Output

For each test case, output a line containing a single integer indicating the distance rounded to the nearest meter.

Sample

Input

1
5
fd 100
lt 120
fd 100
lt 120
fd 100

Output

0

Source: LCS