// Liam Keliher, 2024
//
// TLE submission for problem "Pascal Meets Boole"
//
// Brute force. To find a certain bit, or to count the number of 1's
// in the first r rows, simply fill the rows one by one.


// - BruteForce2 idea: don't repeatedly allocated arrays
//     - either use 2 full-length arrays repeatedly, or just use 1 full-length array

// - BruteForce2 idea: for query type 'B', only fill last row as far as necessary


import java.io.*;

public class TLE_BruteForce1 {
    //---------------------------------------------------------------
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numCases = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder(20*numCases);
        for (int c = 0; c < numCases; c++) {
            String[] tokens = br.readLine().split(" ");
            String op = tokens[0];
            char queryType = tokens[1].charAt(0);
            int r = Integer.parseInt(tokens[2]);

            int[] opArr = new int[4];
            for (int k = 0; k < 4; k++) {
                if (op.charAt(k) == '1') {
                    opArr[k] = 1;
                } // if
            } // for k

            if (queryType == 'B') {
                if (opArr[3] == 1) {
                    sb.append("1\n");
                } // if
                else {
                    int i = Integer.parseInt(tokens[3]);
                    sb.append(getBit(opArr, r, i)).append('\n');
                } // else
            } // if
            else {   // queryType == 'N'
                if (opArr[3] == 1) {
                    sb.append((long)r*(r+1)/2).append('\n');
                } // if
                else {
                    sb.append(countOnes(opArr, r)).append('\n');
                } // else
            } // else
        } // for c
        System.out.print(sb);
    } // main(String[])
    //---------------------------------------------------------------
    static int getBit(int[] opArr, int r, int i) {
        if (i == 1 || i == r) {
            return 1;
        } // if
        int[] prevRow = {1};   // first row
        for (int len = 2; len <= r; len++) {
            int[] currRow = new int[len];
            currRow[0] = 1;
            currRow[len-1] = 1;
            for (int j = 1; j < (len-1); j++) {
                int k = (prevRow[j-1] << 1) | prevRow[j];
                currRow[j] = opArr[k];
            } // for j
            prevRow = currRow;
        } // for len
        return prevRow[i-1];   // convert to 0-based indexing
    } // getBit(int[],int,int)
    //---------------------------------------------------------------
    static long countOnes(int[] opArr, int r) {
        int[] prevRow = {1};   // first row
        long numOnes = 1;
        for (int len = 2; len <= r; len++) {
            int[] currRow = new int[len];
            currRow[0] = 1;
            currRow[len-1] = 1;
            numOnes += 2;
            for (int j = 1; j < (len-1); j++) {
                int k = (prevRow[j-1] << 1) | prevRow[j];
                currRow[j] = opArr[k];
                if (currRow[j] == 1) {
                    numOnes++;
                } // if
            } // for j
            prevRow = currRow;
        } // for len
        return numOnes;
    } // countOnes(int[],int)
    //---------------------------------------------------------------
} // class TL_BruteForce1