#include <bits/stdc++.h>
using namespace std;
int dp[531441], pw2[13], pw3[13], cnt[4096], cnv[4096];
void dfs(int p, int v, string &str, int &ans) {
  if (p == str.length()) {
    ans += dp[v];
  } else {
    if (str[p] == 'A') {
      dfs(p + 1, v, str, ans);
      dfs(p + 1, v + pw3[p], str, ans);
    }
    if (str[p] == 'O') {
      dfs(p + 1, v, str, ans);
    }
    if (str[p] == 'X') {
      dfs(p + 1, v, str, ans);
      dfs(p + 1, v + pw3[p] * 2, str, ans);
    }
    if (str[p] == 'a') {
      dfs(p + 1, v + pw3[p] * 2, str, ans);
    }
    if (str[p] == 'o') {
      dfs(p + 1, v + pw3[p], str, ans);
      dfs(p + 1, v + pw3[p] * 2, str, ans);
    }
    if (str[p] == 'x') {
      dfs(p + 1, v + pw3[p], str, ans);
    }
  }
}
int main(void) {
  int w, n, m;
  cin >> w >> n >> m;
  pw2[0] = pw3[0] = 1;
  for (int i = 1; i <= w; ++i) {
    pw2[i] = pw2[i - 1] * 2;
    pw3[i] = pw3[i - 1] * 3;
  }
  for (int i = 0; i < pw2[w]; ++i) {
    int aux = 0;
    for (int j = 0; j < w; ++j) {
      if (i & pw2[j]) {
        aux += pw3[j];
      }
    }
    cnv[i] = aux;
  }
  while (n--) {
    int x;
    cin >> x;
    ++cnt[x];
  }
  for (int i = 0; i < pw2[w]; ++i) {
    for (int j = 0; j < pw2[w]; ++j) {
      dp[cnv[i] + cnv[j]] += cnt[i] * cnt[j];
    }
  }
  while (m--) {
    string str;
    cin >> str;
    reverse(str.begin(), str.end());
    int ans = 0;
    dfs(0, 0, str, ans);
    cout << ans << "\n";
  }
  return 0;
}
