#include <bits/stdc++.h>
using ll = long long;
constexpr int arr[][6] = {{2, 0, 0, -1, 1, 1}, {0, -1, 1, 1, 2, 0}};
int pw[15], key[5005], sum[600005], idx[15], k, n, m;
char str[15];
ll ans;
void dfs(int pos, int cur = 0, int mask = 0) {
  if (pos >= k) {
    ans += (ll)sum[key[cur]] * sum[mask];
    return;
  }
  for (int i = 0; i < 2; i++) {
    if (~arr[i][idx[pos]])
      dfs(pos + 1, cur | (i << pos), mask + arr[i][idx[pos]] * pw[pos]);
  }
}
int main() {
  scanf("%d%d%d", &k, &n, &m);
  pw[0] = 1;
  for (int i = 0; i < k; i++) pw[i + 1] = pw[i] * 3;
  for (int i = 0; i < 1 << k; i++) {
    int val = 0;
    for (int j = 0; j < k; j++) val += (i >> j & 1) * pw[j];
    key[i] = val;
  }
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    sum[key[x]]++;
  }
  for (int i = 0; i < k; i++) {
    for (int j = 0; j < pw[k]; j++) {
      if (j / pw[i] % 3 == 2) sum[j] += sum[j - pw[i]] + sum[j - pw[i] * 2];
    }
  }
  while (m--) {
    scanf("%s", str);
    for (int i = 0; i < k; i++)
      idx[k - i - 1] = str[i] == 'A'   ? 0
                       : str[i] == 'O' ? 1
                       : str[i] == 'X' ? 2
                       : str[i] == 'a' ? 3
                       : str[i] == 'o' ? 4
                                       : 5;
    ans = 0;
    dfs(0);
    printf("%lld\n", ans);
  }
  return 0;
}
