fun main() {
    val nCases = readln().toInt()
    var n0110Dp = HashMap<Int, Long>()
    for (caseNum in 1..nCases) {
        val tokens = readln().split(" ")
        val funcBits = tokens[0]
        val op = tokens[1]
        val row = tokens[2].toInt()
        if (op.equals("N")) {
            if (funcBits[3]=='1') {
                println((row.toLong()*(row.toLong()+1L)) / 2L)
            } else {
                if (funcBits.equals("0000")) {
                    println(2*(row-1) + 1)
                } else if (funcBits.equals("0010") || funcBits.equals("1010") || funcBits.equals("0100") || funcBits.equals("1100")) {
                    if (row == 1) {
                        println(1)
                    } else {
                        val halfRow = ((row + 1) / 2).toLong()
                        val halfRowTri = (halfRow * (halfRow + 1L)) / 2L
                        var total = 2L * halfRowTri - 1L
                        if (row % 2 == 0) {
                            total += halfRow + 1L
                        }
                        println(total)
                    }
                } else if (funcBits.equals("0110")) {
                    println(nCase0110(row, n0110Dp))
                } else if (funcBits.equals("1110")) {
                    val zeroRowsTotal = (row - ((row + 1) % 2)).toLong()
                    val halfRow = (row / 2).toLong()
                    val oneRowsTotal = halfRow * (halfRow + 1L)
                    println(zeroRowsTotal + oneRowsTotal)
                } else if (funcBits.equals("1000")) {
                    if (row == 1) {
                        println(1)
                    } else {
                        val zeroRowsTotal = (row - (row % 2)).toLong()
                        val halfRow = ((row - 1) / 2).toLong()
                        val oneRowsTotal = halfRow * (halfRow + 1L) - halfRow + 1L  // Off by one  error here
                        println(zeroRowsTotal + oneRowsTotal)
                    }
                }
            }
        } else {
            val position = tokens[3].toInt()
            if (funcBits[3]=='1') {
                println("1")
            } else {
                if (funcBits.equals("0000")) {
                    println(bCase0000(row, position))
                } else if (funcBits.equals("0010") || funcBits.equals("1010")) {
                    println(bCase0010(row, position))
                } else if (funcBits.equals("0100") || funcBits.equals("1100")) {
                    println(bCase0010(row, row - position + 1))
                } else if (funcBits.equals("0110")) {
                    println(bCase0110(row, position))
                } else if (funcBits.equals("1110")) {
                    println(bCase1110(row, position))
                } else if (funcBits.equals("1000")) {
                    println(bCase1000(row, position))
                }
            }
        }
    }
}

fun nCase0110(row: Int, dp: HashMap<Int, Long>): Long {
    if (row == 0) {
        return 0L
    }
    if (row == 1) {
        return 1L
    }
    if (row == 2) {
        return 3L
    }
    if (dp.containsKey(row)) {
        return dp.get(row)!!
    }
    var powLo = 1
    while (2*powLo<row) {
        powLo *= 2
    }
    val whole = 3L * nCase0110(powLo / 2, dp)
    val extra = 2L * nCase0110(row - powLo, dp)
    val total = whole + extra
    dp.put(row, total)
    return return total
}

fun bCase0000(row: Int, position: Int): Int {
    if (position == row || position == 1) {
        return 1
    } else {
        return 0
    }
}
fun bCase0010(row: Int, position: Int): Int {
    if (position == 1 || position == row) {
        return 1
    }
    return (row + position + 1) % 2
}


fun bCase1000(row: Int, position: Int): Int {
    if (position == row || position == 1) {
        return 1
    }
    if (position == 2 || position == row - 1) {
        return 0
    }
    if (row % 2 == 0) {
        return 0
    }
    return 1
}

fun bCase1110(row: Int, position: Int): Int {
    if (position == row || position == 1) {
        return 1
    }
    return (row + 1) % 2
}

fun bCase0110(row: Int, position: Int): Int {
    if (position == row || position == 1) {
        return 1
    }
    var powLo = 1
    while (2*powLo < row) {
        powLo *= 2
    }
    if (powLo == row) {
        return 1
    }
    val middleZeroLow = row - powLo + 1
    val middleZeroHigh = row - middleZeroLow + 1
    if (middleZeroLow <= position && position <= middleZeroHigh) {
        return 0
    }
    if (position < middleZeroLow) {
        return bCase0110(row - powLo, position)
    }
    return bCase0110(row - powLo, row - position + 1)
}