Pascal Meets Boole

문제

Many people are familiar with Pascal's Triangle, a triangular arrangement of integers named after the French mathematician and philosopher Blaise Pascal (1623--1662). If we number the rows of Pascal's Triangle $1,2,3,\dots ,1,\; 2,\; 3,\; \backslash ldots,$ starting from the top, then row $rr$ contains $rr$ elements, which we will number $1,2,\dots ,r1,\; 2,\; \backslash ldots,\; r$ from left to right. The $11$^st and $rr$^th elements in row $rr$ are set equal to $11$, and for $r\ge 3r\; \backslash geq\; 3$ and , element $ii$ in row $rr$ is the sum of elements $i-1i-1$ and $ii$ in row $r-1.r-1.$ More informally, each "non-edge" element is the sum of the two elements immediately above it. Figure J.1(a) depicts the first $88$ rows of Pascal's Triangle.

Figure J.1: (a) Pascal’s Triangle, (b) Pascal-Boole triangle for function $10001000$

But what if we consider a rule other than standard addition for combining values? Since the edge elements are bits $11$'s), a natural option is to use any two-input Boolean function, named after the English mathematician and philosopher George Boole (1815--1864). For example, the Boolean function given by the following truth table generates the triangle depicted in Figure J.1(b) (where we also show the first $88$ rows). In this truth table, $xx$ and $yy$ correspond to elements $i-1i-1$ and $i,i,$ respectively, in row $r-1r-1$, and $f(x,y)f(x,y)$ is the resulting element $ii$ in row $rr$.

$xx$	$yy$	$f(x,y)f(x,y)$
$00$	$00$	$11$
$00$	$11$	$00$
$11$	$00$	$00$
$11$	$11$	$00$

In general, if we label the bits in the rightmost column of any such truth table $b_{00},b_{01},b_{10},b_{11}b\_\{00\},\; b\_\{01\},\; b\_\{10\},\; b\_\{11\}$ from top to bottom, then we can compactly represent a two-input Boolean function by the $44$-bit string $b_{00}{b}_{01}{b}_{10}{b}_{11}\mathrm{.}b\_\{00\}\; b\_\{01\}\; b\_\{10\}\; b\_\{11\}.$ So the example function above is represented by $10001000$.

Your challenge is to answer two kinds of questions about "Pascal-Boole" triangles:

1. For a given Boolean function, $f,f,$ what is the bit in row $rr$, position $ii$?
2. For a given Boolean function, $f,f,$ how many $11$'s are there in the first $rr$ rows?

입력

The first line of input contains an integer, $nn$ $(1\le n\le 250),(1\; \backslash leq\; n\; \backslash leq\; 250),$ the number of test cases. This is followed by $nn$ lines, each of which has one of two forms:

• $ff$ B $rr$ $ii$
• $ff$ N $rr$

In both cases, f is a $44$-bit binary string representing a two-input Boolean function, and $rr$ is an integer $(1\le r\le {10}^6)\mathrm{.}(1\; \backslash leq\; r\; \backslash leq\; 10^6).$ In the first case, $ii$ is an integer $(1\le i\le r)\mathrm{.}(1\; \backslash leq\; i\; \backslash leq\; r).$

출력

For a test case of the form $ff$ B $rr$ $ii$, output a line containing the bit in row $rr$, position $ii$ of the Pascal-Boole triangle generated using $ff$. For a test case of the form $ff$ N $rr$, output a line containing the number of $11$'s in the first $rr$ rows of the Pascal-Boole triangle generated using $ff$.

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

1
28
0