#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

//#ifdef UNIX
typedef unsigned long long DDWORD;
#define FMT1 "%llu\n"
//#else
//typedef unsigned __int64 DDWORD;
//#define FMT1 "%I64u\n"
//#endif

typedef unsigned long DWORD;

DWORD pows2[32];
DWORD pows3[32];

#define MAX_CASES	250

#define ZEROMASK	1
#define ANDMASK		8
#define LEFTMASK	2
#define RTMASK		4

#define MAX_ROWS	1000000000
int opcode, toppow;
DWORD row, elt, mask;
char qtype, opbuf[8];

void MakePows(void)
{
	int i;
	DWORD pow2, pow3;
	pow2 = pow3 = 1;
	for(i = 0; i < 32 ; i++) {
		pows2[i] = pow2;
		pows3[i] = pow3;
		pow2 = 2*pow2;
		pow3 = 3*pow3;
	}
}

int FindTopPow(DWORD row)
{
	int top, bot, cur;
	DWORD low, hi;
	low = 1; hi = pows2[31];
	top = 31; bot = 0; cur = 16; mask = pows2[16];
	while(top > (bot+1)) {
		if(mask == row) {
			return cur;
		} else if(mask < row) {
			bot = cur; cur = (top + bot)/2;
			low = mask; mask = pows2[cur];
		} else {
			top = cur; cur = (top + bot)/2;
			hi = mask; mask = pows2[cur];
		}
	}
	if(mask > row) {
		cur--;
		mask >>= 1;
	} else if(row > (mask << 1)) {
		mask <<= 1;
		cur++;
	}
	return cur;
}

DDWORD CountFunc(DWORD rws)
{
	DDWORD k, ret, rows, factor;
	int level;
	rows = rws;
	if(rows == 1) return 1;
	if(rows == 2) return 3;
	if(opcode == 0) {
		return (2*rows -1);
	} else if((opcode & ANDMASK) != 0) {
		return ((rows*(rows+1))/2);
	} else if(opcode == ZEROMASK) {
		k = (rows - 3)/2;
		return ((k*k) + (2*rows - 1));
	} else if((opcode == 2) || (opcode == 3) || (opcode == 4) || (opcode == 5)) {
		ret = 2*rows - 1;
		if((rows & 1)== 0) {
			k = (rows - 2)/2;
			ret += k*k;
		} else {
			k = (rows - 3)/2;
			ret += k*(k+1);
		}
		return ret;
	} else if (opcode == 6) {
		level = FindTopPow(rws);
		ret = pows3[level]; factor = 2;
		while(level > 0) {
			level--;
			mask >>= 1;
			if((mask & rws) != 0) {
				ret += factor*pows3[level];
				factor = 2*factor;
			}
		}
		return ret;
	} else if (opcode == 7) {
		ret = 2*rows - 1;
		k = (row - 2)/2;
		return (ret + k*(k+1));
	}
	return 0;
}

int ElementFunc(DWORD row, DWORD index)
{
	int level;
	DWORD wid;
	if(opcode == 0) {
		if((elt == 1) || (elt == row)) return 1;
		else return 0;
	} else if((opcode & ANDMASK) != 0) {
		return 1;
	} else if(opcode == ZEROMASK) {
		if((elt == 1) || (elt == row)) return 1;
		else if(((row & 1) != 0) && (elt >=3) && (elt <= row - 2)) return 1;
		else return 0;
	} else if((opcode == 4) || (opcode == 5)) {
		if((elt == 1) || (elt == row)) return 1;
		else if (((row + elt) & 1) == 0) return 1;
		else return 0;
	} else if((opcode == 2) || (opcode == 3)) {
		if((elt == 1) || (elt == row)) return 1;
		else if((elt & 1) != 0) return 1;
		else return 0;
	} else if(opcode == 6) {
		if((elt == 1) || (elt == row)) return 1;
		level = FindTopPow(row);
		wid = row - mask;
		if(wid == 0) return 1;
		if((row & 1)&& (elt == ((row+1)/2))) return 0;
		else if(elt > (row/2)) elt = row - elt + 1;
		row = wid;
		if(elt > row) return 0;
		while(level > 0) {
			level--;
			mask >>= 1;
			if((mask & row) != 0) {
				wid = row - mask;
				if(wid == 0) return 1;
				if((row & 1)&& (elt == ((row+1)/2))) return 0;
				else if(elt > (row/2)) elt = row - elt + 1;
				row = wid;
				if(elt == 1) return 1;
			}
			if(elt > row) return 0;
		}

	} else if(opcode == 7) {
		if((elt == 1) || (elt == row)) return 1;
		else if((row & 1) == 0) return 1;
		else return 0;
	}

	return 0;
}

int ParseInput(char *pbuf, int caseind)
{
	int cnt, base = 1;
	opcode = 0;
	if((cnt = sscanf(pbuf, "%s %c %lu %lu", &(opbuf[0]), &qtype, &row, &elt)) <3){
		fprintf(stderr, "ParseInput: case %d: less that 3 arguments\n", caseind);
		return -11;
	}
	if((qtype != 'B') && (qtype != 'N')) {
		fprintf(stderr, "ParseInput:  case %d: invalid question type \'%c\' not B or N\n", caseind, qtype);
		return -12;
	}
	if((row < 1) || (row > MAX_ROWS)) {
		fprintf(stderr, "ParseInput: case %d: row parameter %lu not in range 1...%d\n", caseind, row, MAX_ROWS);
		return -13;
	}
	if((qtype == 'B') && (cnt < 4)) {
		fprintf(stderr, "ParseInput: case %d: less that 4 arguments for question type B\n", caseind);
		return -14;
	}
	if((qtype == 'B') && ((elt < 1) || (elt > row))) {
		fprintf(stderr, "ParseInput: case %d: element parameter %lu not in range 1...%lu\n", caseind, elt, row);
		return -15;
	}
	for(cnt = 0; cnt < 4; cnt++) {
		if(opbuf[cnt] == '0') {
			base <<= 1;
		} else if(opbuf[cnt] == '1') {
			opcode |= base;
			base <<= 1;
		} else {
			fprintf(stderr, "ParseInput: case %d: opcode char %d (%c) not 0 or 1\n", caseind, cnt, opbuf[cnt]);
			return -16;
		}
	}
	return 0;
}

char inbuf[256];
int main()
{
	int ret, cases, curcase;
	DDWORD ddret;
	MakePows(); // do this once
	if(fgets(&(inbuf[0]), 256, stdin) == NULL) {
		fprintf(stderr, "read failed on num cases\n");
		return -1;
	}
	if(sscanf(&(inbuf[0]), "%d", &cases) != 1) {
		fprintf(stderr, "scan failed on num cases\n");
		return -2;
	}
	if((cases < 1) || (cases > MAX_CASES)) {
		fprintf(stderr, "num cases %d not in range 1... %d\n", cases, MAX_CASES);
		return -3;
	}
	for(curcase = 1; curcase <= cases; curcase++) {
		if(fgets(&(inbuf[0]), 256, stdin) == NULL) {
			fprintf(stderr, "read failed on case %d input\n", curcase);
			return -1;
		}
		if((ret = ParseInput(&(inbuf[0]), curcase)) < 0) {
			return ret;
		}
		if(qtype == 'B') {
			ret = ElementFunc(row, elt);
			printf("%d\n", ret);
		} else {
			ddret = CountFunc(row);
			printf(FMT1, ddret);
		}
	}
	return 0;
}