许多人都熟悉帕斯卡三角形（Pascal’s Triangle），这是一种以法国数学家兼哲学家布莱兹·帕斯卡（Blaise Pascal，1623–1662）命名的整数三角形排列。如果我们从顶部开始，将帕斯卡三角形的行编号为 $1, 2, 3, \dots$，那么第 $r$ 行包含 $r$ 个元素，我们将其从左到右编号为 $1, 2, \dots, r$。第 $r$ 行的第 $1$ 个和第 $r$ 个元素设为 $1$，对于 $r \ge 3$ 且 $1 < i < r$，第 $r$ 行的第 $i$ 个元素是第 $r-1$ 行中第 $i-1$ 个元素和第 $i$ 个元素之和。更通俗地说，每个“非边缘”元素都是其正上方两个元素之和。图 J.1(a) 展示了帕斯卡三角形的前 8 行。
图 J.1: (a) 帕斯卡三角形，(b) 函数 1000 的 Pascal-Boole 三角形
但如果我们考虑使用标准加法以外的规则来组合数值会怎样呢？由于边缘元素是位（$1$），一个自然的选择是使用任何二元布尔函数，该函数以英国数学家兼哲学家乔治·布尔（George Boole，1815–1864）命名。例如，由下表所示真值表给出的布尔函数生成了图 J.1(b) 中描绘的三角形（我们也展示了前 8 行）。在此真值表中，$x$ 和 $y$ 分别对应第 $r-1$ 行中的第 $i-1$ 个和第 $i$ 个元素，$f(x, y)$ 是第 $r$ 行中的结果元素 $i$。
| $x$ | $y$ | $f(x, y)$ |
|---|---|---|
| $0$ | $0$ | $1$ |
| $0$ | $1$ | $0$ |
| $1$ | $0$ | $0$ |
| $1$ | $1$ | $0$ |
通常，如果我们从上到下将任何此类真值表最右侧列的位标记为 $b_{00}, b_{01}, b_{10}, b_{11}$，那么我们可以用 $4$ 位字符串 $b_{00}b_{01}b_{10}b_{11}$ 紧凑地表示一个二元布尔函数。因此，上面的示例函数表示为 $1000$。
你的挑战是回答关于“Pascal-Boole”三角形的两种问题：
- 对于给定的布尔函数 $f$，第 $r$ 行、第 $i$ 个位置的位是什么？
- 对于给定的布尔函数 $f$，前 $r$ 行中有多少个 $1$？
输入格式
输入的第一行包含一个整数 $n$ ($1 \le n \le 250$)，表示测试用例的数量。随后是 $n$ 行，每行具有以下两种形式之一：
- $f \text{ B } r \text{ } i$
- $f \text{ N } r$
在这两种情况下，$f$ 是一个表示二元布尔函数的 $4$ 位二进制字符串，$r$ 是一个整数 ($1 \le r \le 10^6$)。在第一种情况下，$i$ 是一个整数 ($1 \le i \le r$)。
输出格式
对于形式为 $f \text{ B } r \text{ } i$ 的测试用例，输出一行，包含使用函数 $f$ 生成的 Pascal-Boole 三角形中第 $r$ 行、第 $i$ 个位置的位。对于形式为 $f \text{ N } r$ 的测试用例，输出一行，包含使用函数 $f$ 生成的 Pascal-Boole 三角形前 $r$ 行中 $1$ 的数量。
样例
输入 1
3 1000 B 5 3 1111 N 7 0100 B 6 4
输出 1
1 28 0