// Liam Keliher, 2024
//
// Solution for problem "Pascal Meets Boole"
//
// Makes use of patterns in the triangles.


import java.io.*;

public class PascalMeetsBoole {
    //---------------------------------------------------------------
    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]);
            if (queryType == 'B') {
                int i = Integer.parseInt(tokens[3]);
                int bit = -1;
                if (op.charAt(3) == '1') {   // only-1's case
                    bit = 1;
                } // if
                else if (op.equals("0000")) {
                    bit = getBit0000(r, i);
                } // if
                else if (op.equals("0010")) {
                    bit = getBit0010(r, i);
                } // else if
                else if (op.equals("0100")) {
                    bit = getBit0100(r, i);
                } // else if
                else if (op.equals("0110")) {
                    bit = getBit0110(r, i);
                } // else if
                else if (op.equals("1000")) {
                    bit = getBit1000(r, i);
                } // else if
                else if (op.equals("1010")) {
                    bit = getBit1010(r, i);
                } // else if
                else if (op.equals("1100")) {
                    bit = getBit1100(r, i);
                } // else if
                else if (op.equals("1110")) {
                    bit = getBit1110(r, i);
                } // else if
                sb.append(bit).append('\n');
            } // if
            else {   // queryType == 'N'
                long count = -1;
                if (op.charAt(3) == '1') {   // only-1's case
                    count = (long)r*(r+1)/2;   // cast to long to avoid overflow
                } // if
                else if (op.equals("0000")) {
                    count = countOnes0000(r);
                } // if
                else if (op.equals("0010")) {
                    count = countOnes0010(r);
                } // else if
                else if (op.equals("0100")) {
                    count = countOnes0100(r);
                } // else if
                else if (op.equals("0110")) {
                    count = countOnes0110(r);
                } // else if
                else if (op.equals("1000")) {
                    count = countOnes1000(r);
                } // else if
                else if (op.equals("1010")) {
                    count = countOnes1010(r);
                } // else if
                else if (op.equals("1100")) {
                    count = countOnes1100(r);
                } // else if
                else if (op.equals("1110")) {
                    count = countOnes1110(r);
                } // else if
                sb.append(count).append('\n');
            } // else
        } // for c
        System.out.print(sb);
    } // main(String[])
    //---------------------------------------------------------------
    static int getBit0000(int r, int i) {
        return (i == 1 || i == r) ? 1 : 0;
    } // getBit0000(int,int)
    //---------------------------------------------------------------
    static int getBit0010(int r, int i) {
        if (r % 2 == 1) {
            return i % 2;
        } // if
        else {   // r is even
            return (i == 1 || i % 2 == 0) ? 1 : 0;
        } // else
    } // getBit0010(int,int)
    //---------------------------------------------------------------
    static int getBit0100(int r, int i) {
        if (r % 2 == 1) {
            return i % 2;
        } // if
        else {   // r is even
            return (i == r || i % 2 == 1) ? 1 : 0;
        } // else
    } // getBit0100(int,int)
    //---------------------------------------------------------------
    // XOR operation
    static int getBit0110(int r, int i) {
        if (Integer.bitCount(r) == 1) {   // r is a power of 2
            return 1;
        } // if
        else {
            int powerOfTwoBelow = Integer.highestOneBit(r);
            int offset = r - powerOfTwoBelow;
            if (i > offset && i <= (r - offset)) {   // in inverted triangle of 0's
                return 0;
            } // if
            else if (i <= offset) {
                return getBit0110(offset, i);
            } // else if
            else {   // i > (r - offset)
                return getBit0110(offset, i - (r - offset));
            } // else
        } // else
    } // getBit0110(int,int)
    //---------------------------------------------------------------
    // NOR operation
    static int getBit1000(int r, int i) {
        if (r % 2 == 0) {
            return (i == 1 || i == r) ? 1 : 0;
        } // if
        else {   // r is odd
            return (i == 1 || i == r || (i >= 3 && i <= r - 2)) ? 1 : 0;
        } // else
    } // getBit1000(int,int)
    //---------------------------------------------------------------
    static int getBit1010(int r, int i) {
        return getBit0010(r, i);
    } // getBit1010(int,int)
    //---------------------------------------------------------------
    static int getBit1100(int r, int i) {
        return getBit0100(r, i);
    } // getBit1100(int,int)
    //---------------------------------------------------------------
    // NAND operation
    static int getBit1110(int r, int i) {
        if (r % 2 == 0) {
            return 1;
        } // if
        else {   // r is odd
            return (i == 1 || i == r) ? 1 : 0;
        } // else
    } // getBit1110(int,int)
    //---------------------------------------------------------------
    static long countOnes0000(int r) {
        return 2*r - 1;   // only 1's are on left/right edge
    } // countOnes0000(int)
    //---------------------------------------------------------------
    static long countOnes0010(int r) {
        long numOnes = 2*r - 1;   // 1's on left/right edge
        if (r >= 4) {
            long n = (r-2)/2;     // use long to avoid overflow on next line
            numOnes += (r % 2 == 0) ? n*n : n*n + n;   // 1's in interior
        } // if
        return numOnes;
    } // countOnes0010(int)
    //---------------------------------------------------------------
    static long countOnes0100(int r) {
        return countOnes0010(r);
    } // countOnes0100(int)
    //---------------------------------------------------------------
    // XOR operation
    static long countOnes0110(int r) {
        if (r == 1) {
            return 1;
        } // if
        else if (Integer.bitCount(r) == 1) {   // r is a power of 2
            return 3*countOnes0110(r/2);
        } // else if
        else {
            int powerOfTwoBelow = Integer.highestOneBit(r);
            int offset = r - powerOfTwoBelow;
            return countOnes0110(powerOfTwoBelow) + 2*countOnes0110(offset);
        } // else
    } // countOnes0110(int)
    //---------------------------------------------------------------
    // NOR operation
    static long countOnes1000(int r) {
        long numOnes = 2*r - 1;   // 1's on left/right edge
        if (r >= 5) {
            long n = (r-3)/2;     // use long to avoid overflow on next line
            numOnes += n*n;       // 1's in interior
        } // if
        return numOnes;
    } // countOnes1000(int)
    //---------------------------------------------------------------
    static long countOnes1010(int r) {
        return countOnes0010(r);
    } // countOnes1010(int)
    //---------------------------------------------------------------
    static long countOnes1100(int r) {
        return countOnes0010(r);
    } // countOnes1100(int)
    //---------------------------------------------------------------
    // NAND operation
    static long countOnes1110(int r) {
        long numOnes = 2*r - 1;   // 1's on left/right edge
        if (r >= 4) {
            long n = (r-2)/2;     // use long to avoid overflow on next line
            numOnes += n*(n+1);   // 1's in interior
        } // if
        return numOnes;
    } // countOnes1110(int)
    //---------------------------------------------------------------
} // class PascalMeetsBoole