import sys
import math

def ones(f,r):
  if f[3]=='1': # functions with f(1,1)=1
    return r*(r+1)//2
  if f[0:3]=='000': # zero function 
    return 2*r-1
  if f[1:3]=='01' or f[1:3]=='10': # functions with f(0,1)!=f(1,0),f(1,1)=0
    k = (r+1)//2
    return k*(k+1)-1 if r%2==1 else k*(k+2)
  if f[0:3]=='111': # nand
    k = r//2
    return k*(k+1)+r-1 if r%2==0 else k*(k+1)+r
  if f[0:3]=='100':  # nor
    if r <= 2: return [1,3][r-1]
    k = (r-3)//2
    return 2*r-1 + k*k
  return nxor(r) # only case left: xor

def nxor(r):
  if r==0: return 0
  k = int(math.log2(r))
  sum = 3**k
  return sum + 2*nxor(r-2**k)

def bxor(r,i): 
  if i == 1 or i == r: return 1
  k = int(math.log2(r))
  if r==2**k: return 1
  m = r-2**k
  if i <= m: return bxor(m,i)
  if i >= r-m+1: return bxor(m,i+m-r)
  return 0
  
def bit(f,r,i):
  if i==1 or i==r: return 1
  if f[3]=='1': # functions with f(1,1)=1
    return 1
  if f[0:3]=='000': # zero function
    return 0
  if f[1:3]=='01': # functions with f(0,1)=0, f(1,0)=1, f(1,1)=0
    return 1 if (r+i)%2==0 else 0
  if f[1:3]=='10': # functions with f(0,1)=1, f(1,0)=0, f(1,1)=0
    return 1 if i%2==1 else 0
  if f[0:3]=='111': # f(0,0)=f(0,1)=f(1,0)=1, f(1,1) = 0
    return 1 if r%2==0 else 0
  if f[0:3]=='100': # nand
    if r<=2: return 1
    if r%2==0: return 0
    if i==2 or i==r-1: return 0
    return 1
  # only remaining case is f='0110', which is a bit trickier
  return bxor(r,i)

n = int(sys.stdin.readline())
for i in range(n):
  l = sys.stdin.readline().split()
  f = l[0] # f(0,0), f(0,1), f(1,0), f(1,1)

  r = int(l[2]) # row
  if l[1]=='N': # number of ones in first r rows
    print(ones(f,r))
  else: # must be 'B', so get column number and print bit in row i, col j
    j = int(l[3])
    print(bit(f,r,j))