X-Sums Sudoku

An $n\times m$ sudoku puzzle is a grid made of $m\times n$ regions, and each region contains $n\times m$ cells. Hence an $n\times m$ sudoku puzzle contains $nm\times nm$ cells. Every integer from $1$ to $nm$ occurs exactly once in each row, each column, and each region.

List the integers in a row or a column from some direction as a sequence of length $nm$. Let $X$ be the first integer of the sequence. The X-sum is the sum of the first $X$ integers of the sequence.

The figure above shows a $4\times 2$ sudoku puzzle with X-sums. The 7th row, listed from right to left, is $[3,4,1,2,7,8,5,6]$. The first integer $X$ is $3$, so the X-sum of the 7th row from the right is $8=3+4+1$.

Given two positive integers $n$ and $m$, a direction $d$, and an index $x$, find the X-sum of the $x$-th row or $x$-th column from the direction $d$ in the lexicographically smallest $2^n\times 2^m$ sudoku.

For two sudoku puzzles $a$ and $b$ of the same size, $a$ is lexicographically smaller than $b$ if there exist $i$ and $j$ such that $a_{i,j}<b_{i,j}$, $a_{x,y}=b_{x,y}$ for all $x<i$, and $a_{x,y}=b_{x,y}$ for $x=i$ and $y<j$.

The first line contains an integer $T$ ($1\le T\le 10^5$), the number of test cases.

Each test case is one line with two integers $n$ and $m$ ($1\le n, m\le 30$), a string $d$, and an integer $x$ ($1\le x\le 2^{n+m}$). The puzzle size is $2^n\times 2^m$. The direction $d$ is one of left, right, top, or bottom. The index $x$ identifies a row or a column.

For each test case, print one integer on its own line: the X-sum of the $x$-th row or $x$-th column from the direction $d$ in the lexicographically smallest $2^n\times 2^m$ sudoku.

The answer can exceed $2^{64}-1$.