#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
template <class T>
inline void read(T& a) {
  register T x = 0, flag = 1;
  register char ch;
  while (!isdigit(ch = getchar()))
    if (ch == '-') flag = -1;
  while (x = x * 10 + (ch & 15), isdigit(ch = getchar()))
    ;
  a = x * flag;
}
template <class T>
inline void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
template <class T>
inline bool Chkmax(T& x, const T& y) {
  return x < y ? x = y, true : false;
}
template <class T>
inline bool Chkmin(T& x, const T& y) {
  return x > y ? x = y, true : false;
}
const long long maxn = 2501010;
long long n, a[maxn];
long long t[maxn], cnt;
vector<long long> tong[18][5];
inline long long Id(char c) {
  if ('0' <= c && c <= '9')
    return c - '0';
  else
    return c - 'A' + 10;
}
const long long prime[] = {0,  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 long long pk[] = {1224469897, 1503325967, 1336143462, 937397015};
long long m;
long long maxx = 0, maxtmp[27], maxcs[27];
signed main() {
  read(n);
  for (long long i = 0; i < n; i++) {
    read(a[i]);
  }
  for (long long i = 2; i <= 16; i++) {
    long long tmp = 1, cs = 0;
    for (long long j = 1; j <= n; j *= i, tmp *= (i + 1), cs++)
      ;
    for (long long p = 0; p < 4; p++) tong[i][p].resize(tmp, 1);
    maxtmp[i] = tmp;
    maxcs[i] = cs;
  }
  for (long long i = 2; i <= 16; i++) {
    for (long long j = 0; j < n; j++) {
      long long tmp = j, asd = 0;
      cnt = 0;
      while (tmp) {
        t[++cnt] = tmp % i;
        tmp /= i;
      }
      if (cnt == 0) t[++cnt] = 0;
      for (long long p = cnt; p >= 1; p--) asd = asd * (i + 1) + t[p];
      for (long long k = 0; k < 4; k++)
        tong[i][k][asd] = tong[i][k][asd] * a[j] % pk[k];
    }
    long long tmp = 1, cs = 0;
    for (long long k = 0; k < 4; k++)
      for (long long j = 0; j <= maxtmp[i]; j++) {
        long long pl = j, tt = 1;
        while (pl) {
          long long p = pl % (i + 1);
          if (p == i) {
            for (long long cxy = 0; cxy < i; cxy++) {
              tong[i][k][j] =
                  (tong[i][k][j] * tong[i][k][j - tt * i + cxy * tt]) % pk[k];
            }
            break;
          }
          tt = tt * (i + 1);
          pl /= (i + 1);
        }
      }
  }
  read(m);
  for (long long i = 1; i <= m; i++) {
    long long k, c;
    read(k);
    string s;
    cin >> s;
    read(c);
    long long asd = 0, ok = 0;
    for (long long i = 1; i <= 25; i++) {
      long long pos = s.size() - 1, tmp = 1;
      long long ks;
      for (long long ss = 0; ss < 4; ss++)
        if (pk[ss] % prime[i] == 0) {
          ks = ss;
          break;
        }
      long long asd = 0;
      long long sss = 0;
      for (long long p = 0; p < s.size(); p++) {
        if (s[p] != '?') sss = sss * (k + 1) + Id(s[p]);
        if (sss >= maxtmp[k]) {
          tmp = 1;
          goto loop;
        }
      }
      if (sss >= maxtmp[k])
        tmp = 1;
      else {
        for (long long p = max(0ll, (long long)s.size() - maxcs[k]);
             p < s.size(); p++) {
          if (s[p] == '?')
            asd = asd * (k + 1) + k;
          else
            asd = asd * (k + 1) + Id(s[p]);
        }
        tmp = tong[k][ks][asd] % prime[i];
      }
    loop:
      if ((tmp + c) % prime[i] == 0) {
        cout << prime[i] << endl;
        ok = 1;
        break;
      }
    }
    if (ok == 0) {
      puts("-1");
    }
  }
  return 0;
}
