#include "bits/stdc++.h"
using namespace std;

int n, q;        // n: 煎饼数量，q: 查询数量
int tot;         // 总状态数 = 3^n
vector<int> d;   // 存储每个状态到目标状态的最短距离

// 将字符串转换为状态ID
int sid(const string& s) {
    int id = 0;
    for (char c : s) {
        id = id * 3 + (c - 'A');  // A=0, B=1, C=2
    }
    return id;
}

// 检查是否是目标状态A...A B...B C...C）
bool isd(const string& s) {
    for (int i = 0; i + 1 < s.size(); i++) {
        if (s[i] > s[i + 1]) return false;  // 如果发现逆序，不是目标状态
    }
    return true;
}

// 将状态ID转换为字符串
string id_str(int id) {
    string s(n, ' ');
    int x = id;
    for (int i = n - 1; i >= 0; i--) {
        s[i] = 'A' + (x % 3);
        x /= 3;
    }
    return s;
}

int main() {
    cin >> n >> q;
    
    tot = 1;
    for (int i = 0; i < n; i++) tot *= 3;
    d.resize(tot, -1);  // 初始化，-1表示未访问
    
    // BFS预处理：从所有目标状态开始反向搜索
    queue<int> qu;
    for (int id = 0; id < tot; id++) {
        string s = id_str(id);
        if (isd(s)) {      // 如果是目标状态
            d[id] = 0;     // 距离为0
            qu.push(id);   // 加入队列
        }
    }
    
    // BFS主循环
    while (!qu.empty()) {
        int u = qu.front();  // 当前状态ID
        qu.pop();
        
        string s = id_str(u);  // 当前状态对应的字符串
        
        // 尝试所有可能的操作k：翻转前k个煎饼
        for (int k = 2; k <= n; k++) {
            string t = s;
            reverse(t.begin(), t.begin() + k);  // 翻转前k个字符
            
            int vid = sid(t);  // 新状态ID
            if (d[vid] == -1) {  // 如果新状态未被访问
                d[vid] = d[u] + 1;  // 更新距离
                qu.push(vid);       // 加入队列
            }
        }
    }
    
    // 处理查询
    for (int i = 0; i < q; i++) {
        string s;
        cin >> s;
        int id = sid(s);      // 将输入字符串转换为状态ID
        cout << d[id] << "\n"; // 输出最短操作次数
    }
    
    return 0;
}