// 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.
//
// Same as BruteForce1.java, but only allocates a single array of maximum length
// to hold a row of the triangle, and then uses it repeatedly, thereby avoiding
// repeated allocations of arrays of increasing length.


import java.io.*;

public class TLE_BruteForce2 {
    static final int MAX = 1_000_000;
    static final int[] row = new int[MAX];
    //---------------------------------------------------------------
    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
        row[0] = 1;   // first row
        int oldPrevBit = 1;
        for (int len = 2; len <= r; len++) {
            row[len-1] = 1;
            for (int j = 1; j < (len-1); j++) {
                int k = (oldPrevBit << 1) | row[j];
                oldPrevBit = row[j];
                row[j] = opArr[k];
            } // for j
        } // for len
        return row[i-1];   // convert to 0-based indexing
    } // getBit(int[],int,int)
    //---------------------------------------------------------------
    static long countOnes(int[] opArr, int r) {
        row[0] = 1;   // first row
        int oldPrevBit = 1;
        long numOnes = 1;
        for (int len = 2; len <= r; len++) {
            row[len-1] = 1;
            numOnes += 2;
            for (int j = 1; j < (len-1); j++) {
                int k = (oldPrevBit << 1) | row[j];
                oldPrevBit = row[j];
                row[j] = opArr[k];
                if (row[j] == 1) {
                    numOnes++;
                } // if
            } // for j
        } // for len
        return numOnes;
    } // countOnes(int[],int)
    //---------------------------------------------------------------
} // class TL_BruteForce2