#include <bits/stdc++.h>
const int p[] = {2,  3,  5,  7,  11, 13, 17, 19, 23, 29, 31, 37, 41,
                 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
const int idx[] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1,
                   1, 1, 2, 2, 3, 2, 3, 3, 3, 3, 2, 2};
const int mod[] = {300690390, 2044926619, 1808691197, 2073080791};
struct data {
  int num[4];
  data(long long x = 0) {
    for (int i = 0; i < 4; i++) num[i] = x % mod[i];
  }
  inline data operator*(const data &a) const {
    data res;
    for (int i = 0; i < 4; i++)
      res.num[i] = (long long)num[i] * a.num[i] % mod[i];
    return res;
  }
  inline data operator*=(const data &a) { return *this = *this * a; }
};
std::vector<data> dp[25];
int n, len[25], pw[25], arr[25];
long long val[10005];
inline void init(int bs) {
  int cur = bs, cnt = bs + 1;
  len[bs] = 1;
  while (cur < n) {
    cur *= bs;
    cnt *= bs + 1;
    len[bs]++;
  }
  dp[bs].resize(cnt);
  pw[0] = 1;
  for (int i = 1; i < len[bs]; i++) pw[i] = pw[i - 1] * (bs + 1);
  for (int mask = 0; mask < cnt; mask++) {
    dp[bs][mask] = 1;
    int x = mask;
    for (int i = 0; i < len[bs]; i++) {
      arr[i] = x % (bs + 1);
      x /= bs + 1;
    }
    int pos = len[bs] - 1;
    while (pos >= 0 && arr[pos] != bs) pos--;
    if (pos < 0) {
      x = 0;
      for (int i = len[bs] - 1; i >= 0; i--) x = x * bs + arr[i];
      if (x < n) dp[bs][mask] = val[x];
    } else {
      for (int i = 1; i <= bs; i++) dp[bs][mask] *= dp[bs][mask - i * pw[pos]];
    }
  }
}
char str[35];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%lld", val + i);
  for (int i = 2; i <= 16; i++) init(i);
  int q;
  scanf("%d", &q);
  while (q--) {
    int bs;
    long long dt;
    scanf("%d%s%lld", &bs, str, &dt);
    int mask = 0, mask_len = strlen(str), ans = -1;
    for (int i = std::max(mask_len - len[bs], 0); i < mask_len; i++)
      mask = mask * (bs + 1) + (str[i] == '?'   ? bs
                                : str[i] <= '9' ? str[i] - '0'
                                                : str[i] - 'A' + 10);
    data res = dp[bs][mask];
    for (int i = 0; i < 25; i++) {
      if (!((dt + res.num[idx[i]]) % p[i])) {
        ans = p[i];
        break;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
