An sudoku puzzle is a grid consisting of regions, and each region contains cells. Hence an sudoku puzzle contains cells. Every integer from to occurs exactly once in each row, each column, and each region of an sudoku puzzle.

Listing the integers in a row or a column starting from some direction as a sequence of length , is the first integer of the sequence, and X-sum is the sum of the first integers of the sequence.



The above figure is a sudoku puzzle with X-sums. The -th row listed from right to left is and the first integer is , so the X-sum of the -th row from the direction right is .

Given two positive integers and , a direction , and an index , you need to find the X-sum of the -th row or -th column from the direction in the lexicographically smallest  sudoku.

Denoting as the -th row and the -th column of a sudoku puzzle , a sudoku puzzle is lexicographically smaller than a sudoku puzzle of the same size if there exists and satisfying that , that for all , and that for all and . You can find that the above is the lexicographically smallest sudoku puzzle.

There are multiple test cases. The first line of input contains an integer (), the number of test cases.

For each test case:

The only line contains two integers  and  (, ), a string , and an integer  ().  is the size of the sudoku puzzle.  is the direction of X sum, and it is one of "left", "right", "top", and "bottom".  is the index of a row or a column.

For each test case:

Output an integer -- the X-sum of the -th row or -th column from the direction  in the lexicographically smallest  sudoku.

Note that the answer may exceed . Consider using __int128_t in C++, BigInteger in Java or Kotlin, or int in Python.

4
2 1 top 1
2 1 bottom 2
2 1 left 3
2 1 right 4

1
34
27
3

4
11 19 top 1053766555
12 26 top 230781535210
14 10 right 8344647
7 30 right 70120568170

565741033271081135
31719572400444316026492
112693473538824
477453505821905419941