#include <bits/stdc++.h>
using namespace std;
long long inline read() {
  long long a = 0, c = getchar();
  for (; !isdigit(c); c = getchar())
    ;
  for (; isdigit(c); a *= 10, a += c ^ 48, c = getchar())
    ;
  return a;
}
string inline readstr() {
  string s;
  char c = getchar();
  for (; c != '?' && !isalnum(c); c = getchar())
    ;
  for (; c == '?' || isalnum(c); s += c, c = getchar())
    ;
  return s;
}
void inline write(int a, char c = '\n') {
  a < 0 ? (putchar(45), a = -a) : 0;
  int s = 0, d[10] = {0};
  for (; a; d[s++] = a % 10, a /= 10)
    ;
  for (s = s ? s : 1; s; putchar(d[--s] + 48))
    ;
  putchar(c);
}
const int nsz = 1e4, msz = 3e4, psz = 25, modsz = 5, msksz = 4782969;
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 mod[] = {3118414, 8795307, 19720385, 41281849, 103256791};
int n, m, len, to, dp[msksz + 5], ans[msz + 5], cur[nsz + 5];
long long a[nsz + 5];
struct query {
  int id, b;
  long long c;
  string s;
  query() {}
  query(int id) {
    this->id = id;
    b = read();
    s = readstr();
    c = read();
  }
};
query dat[msz + 5];
bool inline operator<(const query a, const query b) { return a.b < b.b; }
int inline to_int(char c) { return isdigit(c) ? c ^ 48 : c - 'A' + 10; }
int inline calc_len(int b) {
  int res = 0;
  for (int tmp = n; tmp; tmp /= b, ++res)
    ;
  return res;
}
int inline qpow(int a, int p) {
  int res = 1;
  for (; p; p >>= 1) {
    if (p & 1) {
      res *= a;
    }
    a *= a;
  }
  return res;
}
int main() {
  n = read();
  for (int i = 0; i < n; ++i) {
    a[i] = read();
  }
  m = read();
  for (int i = 1; i <= m; ++i) {
    dat[i] = query(i);
  }
  sort(dat + 1, dat + m + 1);
  memset(ans, -1, sizeof(ans));
  int cur = 1, pre = cur;
  for (int b = 2; b <= 16; ++b) {
    len = calc_len(b), to = qpow(b + 1, len) - 1;
    for (int mid = 0; mid < modsz; ++mid) {
      int mod = ::mod[mid];
      for (int S = 0; S <= to; ++S) {
        int tmp = S, fS = 0, pos = -1;
        for (int i = len - 1; i >= 0; --i) {
          int c = tmp % (b + 1);
          if (c == b) {
            pos = i;
            break;
          }
          fS += c * qpow(b, len - i - 1);
          tmp /= b + 1;
        }
        if (pos == -1) {
          dp[S] = fS < n ? a[fS] % mod : 1;
        } else {
          int del = qpow(b + 1, len - pos - 1);
          dp[S] = 1;
          for (int k = 1; k <= b; ++k) {
            dp[S] = (long long)dp[S] * dp[S - k * del] % mod;
          }
        }
      }
      for (cur = pre; cur <= m; ++cur) {
        if (dat[cur].b != b) break;
        bool f = 1;
        int id = dat[cur].id, S = 0, val, del = dat[cur].c % mod;
        string s = dat[cur].s;
        reverse(s.begin(), s.end());
        for (; s.size() < len; s += '0')
          ;
        if (s.size() > len) {
          for (int i = len; i <= s.size() - 1; ++i) {
            f &= (s[i] == '?') || (s[i] == '0');
          }
          s = s.substr(0, len);
        }
        for (int i = s.size() - 1; i >= 0; --i) {
          S *= b + 1;
          S += (s[i] == '?') ? b : to_int(s[i]);
        }
        val = f ? dp[S] : 1;
        for (int k = mid; k < psz; k += 5) {
          int p = ::p[k];
          if ((val + (dat[cur].c % p)) % p == 0) {
            if (ans[id] == -1 || ans[id] > p) {
              ans[id] = p;
            }
            break;
          }
        }
      }
    }
    pre = cur;
  }
  for (int i = 1; i <= m; ++i) {
    write(ans[i]);
  }
}
