题目描述

许多人都熟悉杨辉三角（Pascal's Triangle），这个三角形整数排列以法国数学家兼哲学家 Blaise Pascal（1623–1662）命名。

从顶端开始把各行编号为 $1,2,3,\ldots$，则第 $r$ 行包含 $r$ 个元素，从左到右编号为 $1,2,\ldots,r$。第 $r$ 行的第 $1$ 个和第 $r$ 个元素都等于 $1$；当 $r\ge 3$ 且 $1<i<r$ 时，第 $r$ 行第 $i$ 个元素等于第 $r-1$ 行第 $i-1$ 个与第 $i$ 个元素之和。通俗地说，每个非边界元素都是它正上方两个元素之和。图 1(a) 展示了杨辉三角的前 $8$ 行。

如果不用普通加法来组合数值，会怎样呢？由于边界元素都是比特 $1$，一种自然选择是使用任意二输入布尔函数——布尔函数得名于英国数学家兼哲学家 George Boole（1815–1864）。例如，下面真值表给出的布尔函数会生成图 1(b) 中的三角形，图中同样画出了前 $8$ 行。表中的 $x,y$ 分别对应第 $r-1$ 行的第 $i-1$、第 $i$ 个元素，$f(x,y)$ 是第 $r$ 行所得的第 $i$ 个元素。

一般地，把任意此类真值表最右列的比特从上到下记为 $b_{00},b_{01},b_{10},b_{11}$，就可以用四位字符串 $b_{00}b_{01}b_{10}b_{11}$ 简洁表示一个二输入布尔函数。因此，上例函数表示为 1000。

请回答两类关于“Pascal–Boole 三角”的问题：

1. 给定布尔函数 $f$，第 $r$ 行第 $i$ 个位置的比特是什么？
2. 给定布尔函数 $f$，前 $r$ 行一共有多少个 $1$？

:::align{center} :::

输入格式

第一行包含一个整数 $n$（$1\le n\le 250$），表示测试用例数量。

接下来的 $n$ 行中，每行为以下两种形式之一：

1. $f$ B $r$ $i$；
2. $f$ N $r$。

两种形式中，$f$ 都是表示二输入布尔函数的四位二进制字符串，$r$ 是满足 $1\le r\le 10^6$ 的整数。第一种形式中另有整数 $i$，满足 $1\le i\le r$。

输出格式

对于形如 $f$ B $r$ $i$ 的测试用例，输出由 $f$ 生成的 Pascal–Boole 三角中第 $r$ 行第 $i$ 个位置的比特。

对于形如 $f$ N $r$ 的测试用例，输出由 $f$ 生成的 Pascal–Boole 三角前 $r$ 行中 $1$ 的总数。

3
1000 B 5 3
1111 N 7
0100 B 6 4

1
28
0