一个 $n \times m$ 数独是一个由 $m \times n$ 个区域组成的网格，每个区域包含 $n \times m$ 个单元格。因此，一个 $n \times m$ 数独包含 $nm \times nm$ 个单元格。在 $n \times m$ 数独中，从 $1$ 到 $nm$ 的每个整数在每一行、每一列和每一个区域中都恰好出现一次。

将一行或一列中的整数按某个方向列出，形成一个长度为 $nm$ 的序列，设 $X$ 为该序列的第一个整数，则 X-sum 为该序列前 $X$ 个整数之和。

上图是一个 $4 \times 2$ 数独及其 X-sum。第 7 行从右向左列出为 $[3, 4, 1, 2, 7, 8, 5, 6]$，第一个整数 $X$ 为 3，因此该行从右侧方向的 X-sum 为 $8 = 3 + 4 + 1$。

给定两个正整数 $n$ 和 $m$，一个方向 $d$，以及一个索引 $x$，你需要求出字典序最小的 $2^n \times 2^m$ 数独中，从方向 $d$ 数起的第 $x$ 行或第 $x$ 列的 X-sum。

设 $a_{i,j}$ 为数独 $a$ 的第 $i$ 行第 $j$ 列的元素，如果存在 $i$ 和 $j$ 满足 $a_{i,j} < b_{i,j}$，且对于所有 $x < i$ 有 $a_{x,y} = b_{x,y}$，以及对于 $x = i$ 且所有 $y < j$ 有 $a_{x,y} = b_{x,y}$，则称数独 $a$ 的字典序小于数独 $b$。你可以发现上图即为字典序最小的 $4 \times 2$ 数独。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T (1 \le T \le 10^5)$，表示测试数据的组数。

对于每组测试数据： 仅一行，包含两个整数 $n$ 和 $m (1 \le n, m \le 30)$，一个字符串 $d$，以及一个整数 $x (1 \le x \le 2^{n+m})$。 这里，$2^n \times 2^m$ 是数独的大小；$d$ 是 X-sum 的方向，取值为 “left”、“right”、“top” 或 “bottom” 之一；$x$ 是行或列的索引。

输出格式

对于每组测试数据： 输出一个整数：字典序最小的 $2^n \times 2^m$ 数独中，从方向 $d$ 数起的第 $x$ 行或第 $x$ 列的 X-sum。

注意，答案可能超过 $2^{64} - 1$。在 C++ 中请考虑使用 __int128_t，在 Java 或 Kotlin 中使用 BigInteger，或在 Python 中使用 int。

样例

样例输入 1

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

样例输出 1

1
34
27
3

样例输入 2

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

样例输出 2

565741033271081135
31719572400444316026492
112693473538824
477453505821905419941