#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

/* Board size limits: 4x4 to 10x10. We deal with 32x32 coordinates (1024 bits). */
constexpr unsigned W=32, H=32, Bits=W*H, CX=10, CY=10;
unsigned density = 1;

struct Pattern
{
    typedef std::uint_fast32_t Word;
    static constexpr unsigned nbits = W*H, nwordbits = sizeof(Word)*8;
    static constexpr unsigned nwordsperline = (W+nwordbits-1)/nwordbits, nlines = H;

    Word data[nlines * nwordsperline]{};
    void clear()                    { std::fill_n(data, nlines*nwordsperline, 0); }
    void set(unsigned x,unsigned y) { data[y*nwordsperline + x/nwordbits] |= Word(1) << (x % nwordbits); }

    // King, rook, bishop, queen, horse
    void make_k() { for(int py=-1; py<=1; ++py) for(int px=-1; px<=1; ++px) set(CX+px,CY+py); }
    void make_r() { for(int p=-10; p<=10; ++p) { set(CX+p, CY);   set(CX,   CY+p); } }
    void make_b() { for(int p=-10; p<=10; ++p) { set(CX-p, CY-p); set(CX-p, CY+p); } }
    void make_q() { make_r(); make_b(); }
    void make_h() { for(int a=-2; a<=2; a+=4) for(int b=-1; b<=1; b+=2) { set(CX+a,CY+b); set(CX+b,CY+a); } }

    void dump(unsigned sizex, unsigned sizey)
    {
        for(unsigned y=0; y<H; ++y)
        {
            if(y == CY || y == (CY+sizey))
            {
                for(unsigned x=0; x<W; ++x) { if(x == CX || x == (CX+sizex)) { std::cout << '+'; } std::cout << '-'; }
                std::cout << std::endl;
            }
            for(unsigned x=0; x<W; ++x)
            {
                if(x == CX || x == (CX+sizex)) std::cout << '|';
                std::cout << ((data[y*nwordsperline + x/nwordbits] & (1u << (x%nwordbits))) ? 'X' : '.');
            }
            std::cout << "\n";
        }
    }

    // Offset the pattern towards right and down
    void moveby(unsigned px, unsigned py)
    {
        // Move down and shift horizontally
        for(unsigned sourcey = nlines-py; sourcey-- > 0; )
        {
            Word* srcline = &data[(sourcey   )*nwordsperline];
            Word* dstline = &data[(sourcey+py)*nwordsperline];
            // To rotate right by 5 bits (bits are shifted left, overflow towards right):
            //   xxxxxxxx 76543210 FEDCBA98 yyyyyyyy
            //   xxx----- 210xxxxx A9876543 yyyFEDCB
            // So, right-shift: word[1] = (word[1] << N) | (word[0] >> (w-N))
            unsigned woffset = px / nwordbits, bitoffset = px % nwordbits;
            for(unsigned dstword = nwordsperline; dstword-- > 0; )
            {
                unsigned srcword  = (dstword >= (woffset+0)) ? srcline[dstword - (woffset    )] : 0;
                unsigned srcwordp = (dstword >= (woffset+1)) ? srcline[dstword - (woffset + 1)] : 0;
                unsigned word = (srcword << bitoffset);
                if(bitoffset != 0) word |= (srcwordp >> (nwordbits-bitoffset));
                dstline[dstword] = word;
            }
            // Clear removed words
            std::fill_n(dstline, woffset, 0);
        }
        // Clear the top lines
        std::fill_n(data+0, py*nwordsperline, 0);
    }

    // Test patterns
    bool test(unsigned x, unsigned y) const
    {
        return data[(y+CY)*nwordsperline + (x+CX)/nwordbits] & Word(1) << ((x+CX) % nwordbits);
    }

    bool test(const Pattern& b) const
    {
        for(unsigned n=0; n<nlines * nwordsperline; ++n)
        {
            if(!data[n]) continue;
            if(data[n] & b.data[n]) return true;
        }
        return false;
    }
    void mix(const Pattern& b)
    {
        for(unsigned n=0; n<nlines * nwordsperline; ++n) data[n] |= b.data[n];
    }
};

static void Fit(const Pattern& pieces, const Pattern& dangers,
                std::vector<unsigned>& positions,
                std::vector<unsigned>& record,
                unsigned sizex,unsigned sizey, const Pattern& model,
                unsigned first)
{
    const unsigned ncoords = sizex*sizey;

    for(; first < ncoords; ++first)
    {
        if(positions.size() + (ncoords-first)/density < record.size()) break;

        if(dangers.test(first%sizex, first/sizex)) continue;

        Pattern test_dangers = model;
        test_dangers.moveby(first%sizex, first/sizex);
        if(pieces.test(test_dangers))
        {
            continue;
        }

        test_dangers.mix(dangers);

        Pattern test_pieces = pieces;
        test_pieces.set(CX+first%sizex, CY+first/sizex);

        positions.push_back(first);
        if(positions.size() > record.size())
        {
            record = positions;
        }

        Fit(test_pieces, test_dangers, positions,record, sizex,sizey, model, first+1);
        positions.pop_back();
    }
}

static void Find(unsigned sizex,unsigned sizey, const Pattern& model)
{
    Pattern pieces,dangers;
    std::vector<unsigned> positions;
    std::vector<unsigned> record;

    Fit(pieces,dangers, positions,record, sizex,sizey, model, 0);

    std::cout << record.size() << std::endl;
}

int main()
{
    unsigned nproblems; std::cin >> nproblems;
    while(nproblems-- > 0 && std::cin.good())
    {
        std::string what;
        unsigned sizex=0, sizey=0;
        std::cin >> what >> sizex >> sizey;

        Pattern model;
        if(what=="K")      { //model.make_k(); density = 4; }
                             std::cout << int(((sizex+1)/2)*((sizey+1)/2)) << std::endl; continue; }
        else if(what=="Q") { model.make_q(); density = 4; }
        else if(what=="k") { //model.make_h(); density = 2; }
                             std::cout << int((sizex*sizey+1)/2) << std::endl; continue; }
        else if(what=="r") { std::cout << std::min(sizex,sizey) << std::endl; continue; }
        else { std::cerr << "Unknown model: " << what << std::endl; break; }

        Find(sizex,sizey, model);
    }
}